La complessità della moltiplicazione di due matrici triangolari inferiori

Question

So che il limite inferiore della moltiplicazione di due matrici complete è Ω (n^2). Matrix multiplication

Ho cercato di dimostrare che il limite inferiore della moltiplicazione di due matrici triangolari inferiori utilizza il metodo di trasformazione del problema.

Il mio pensiero iniziale è che per (1) trasformare la matrice triangolare inferiore, (2) stimare la complessità temporale di tale trasformazione.

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

Ora, devo solo dimostrare O(lower_triangular_matrix_transformation(n)) e ho bisogno di fare matrice triangolare essere una matrice completa quindi ho lasciato questa matrice triangolare moltiplicato per una variazione di sé, dire trasposizione, per semplicità.

Il motivo è che il quadrato di una matrice triangolare inferiore è ancora una matrice triangolare inferiore e una matrice triangolare inferiore moltiplicata per la sua variazione trasposta è una "matrice completa".

Quindi ho solo bisogno di analizzare la complessità di una matrice triangolare moltiplicata per la sua variazione trasposta.

Qualcuno potrebbe indicare se il mio pensiero è "ragionevole"?

Answer 1

Stavo pensando che la soluzione potrebbe essere quella di trasformare A in A + A '. Sia la complessità delle operazioni di trasposizione che di plus è O (n^2). Quindi, O (lower_triangular_matrix_transformation (n)) = n^2. Poiché il limite inferiore di A A e quello di (A + A ') (A + A') sono anche Ω (n^2), T (lower_triangular_matrix_multiplication (n))> Ω (full_matrix_multiplication (n)) -O (lower_triangular_matrix_transformation (n)), che significa che il limite inferiore della matrice triangolare e quello della matrice completa sono identici.

Q.E.D.

Answer 2

Non sono convinto che la costruzione di un algoritmo sia una prova sufficiente per il limite inferiore, in quanto non è stato possibile escludere che esisterebbe un algoritmo diverso con una complessità inferiore.

È chiaro che il limite inferiore non sarà superiore a O (n^2) in quanto la moltiplicazione generale sarebbe sempre applicabile a matrici_linea inferiori (ltm).

Ora, come qualsiasi trasformazione di una matrice arbitraria in uno o più ltm è di per sé un'operazione di complessità di O (n^2), non possiamo dedurre che tale algoritmo non esiste.

Lo schema del ragionamento sembra suggerire che l'aggiunta di complessità stia seguendo regole "normali" aritmetiche. Questo non è il caso!
La complessità risultante è sempre (almeno) il massimo delle complessità delle parti degli algoritmi.

Quindi il tuo ragionamento sembra non essere valido.

Si potrebbe provare una delle seguenti opzioni:

1. costruire un algoritmo con complessità inferiore (prova di essere esistenza)
   il bersaglio è O (LTM) < O (n^2)
2. trovare un trasformazione che ha complessità < O (n^2) e che produce ltm. Quindi qualsiasi algoritmo per la moltiplicazione ltm che ha una complessità inferiore fornirebbe un algoritmo per matrici arbitrarie con complessità Ciò contraddirebbe la tua proposta iniziale.
   Ciò tuttavia richiede una trasformazione di sufficiente bassa complessità. Se questo non è noto. L'argomento non è utilizzabile.

Per me sembra che il passo da T() + O()> O (n^2) non sia ben collegato. E da questo si conclude la conclusione di dover semplicemente provare (O (ltm)).