Сложность умножения двух нижних треугольных матриц

Я знаю, что нижняя граница умножения двух полных матриц равна Ω (n ^ 2). Матричное умножение

Я пытался доказать, что нижняя граница умножения двух нижних треугольных матриц с использованием метода преобразования задачи.

Мое первоначальное мышление состоит в том, чтобы (1) преобразовать нижнюю треугольную матрицу, (2) оценить временную сложность такого преобразования.

T(lower_triangular_matrix_multiplication(n))+O(lower_triangular_matrix_transformation(n))>Ω(full_matrix_multiplication(n)) = Ω(n^2)

Теперь мне нужно доказать O(lower_triangular_matrix_transformation(n)), и мне нужно, чтобы треугольная матрица была полной матрицей, поэтому просто позвольте этой треугольной матрице умножить на ее вариацию, скажем, транспонировать для простоты.

Причина в том, что квадрат нижней треугольной матрицы все еще является нижней треугольной матрицей, а нижняя треугольная матрица, умноженная на ее транспонированное изменение, является "полной матрицей".

Поэтому мне нужно только проанализировать сложность треугольной матрицы, умноженной на ее транспонированную вариацию.

Может ли кто-нибудь указать, разумно ли мое мышление?

Ответ 1

Я не убежден, что построение алгоритма является достаточным доказательством для нижней границы, поскольку по-прежнему нельзя исключить, что существовал бы другой алгоритм с меньшей сложностью.

Ясно, что нижняя граница не будет больше O (n ^ 2), поскольку общее умножение всегда будет применимо к lower_triangle_matrices (ltm).

Теперь, поскольку любое преобразование произвольной матрицы в одну или более ltm само по себе является операцией сложности O (n ^ 2), мы не можем вывести, что никакого такого алгоритма не существует.

Ваш контур рассуждений, по-видимому, предполагает, что добавление сложностей соответствует "нормальным" арифметическим правилам. Это не так! Результирующая сложность всегда является (по крайней мере) максимальным сложностью частей алгоритмов.

Итак, ваши рассуждения, кажется, не звучат.

Вы можете попробовать одно из следующих действий:

построить алгоритм с меньшей сложностью (доказательство существования)
когда мишень O (ltm) O (N ^ 2)
найти преобразование, имеющее сложность < O (n ^ 2) и что дает LTM. Тогда любой алгоритм умножения ltm, который имеет более низкую сложность обеспечит алгоритм для произвольных матриц со сложностью Это противоречило бы вашему первоначальному предложению. Однако это требует трансформации достаточно низкой сложности. Если это неизвестно. Аргумент неприменим.

Мне кажется, что шаг от T() + O() > O (n ^ 2) не является обоснованным. И из этого следует сделать вывод, что нужно просто доказать (O (ltm)).

Ответ 2

Я думал, что решением может быть преобразование A в + A '. И сложность операций транспонирования, и плюс равна O (n ^ 2). Итак, O (lower_triangular_matrix_transformation (n)) = n ^ 2. Поскольку нижняя грань АА и одна из (А + А ') (А + А') также Q (n ^ 2), T (lower_triangular_matrix_multiplication (n)) > Ω (full_matrix_multiplication (n)) - O (lower_triangular_matrix_transformation (n)), что означает, что нижняя грань треугольной матрицы и одна полная матрица идентичны.

Q.E.D.