O número mínimo de operações aritméticas para calcular o determinante

Houve algum trabalho em encontrar o número mínimo de operações aritméticas elementares necessários para calcular o determinante de um por matriz para pequeno e fixo ? Por exemplo, . $n$ $n$ $n$ $n=5$

cc.complexity-theory linear-algebra determinant Lembik
fonte

Perguntei a especialistas sobre isso e, aparentemente, ainda não se sabe se são necessárias 9 multiplicações para calcular o determinante de uma matriz 3x3.

Jeffrey Shallit

@JeffreyShallit Se

9

$9$ for possível, isso já é interessante (como é menor que

n^{3}

$n^3$ por exemplo). Que tal

n = 4

$n=4$ ?

Lembik

Não, nada interessante. 9 multiplicações para n = 3 seguem a expansão por menores. Para n = 4 novamente, a expansão por menores dá 40. Não sei como fazê-lo em menos de 40 multiplicações.

Jeffrey Shallit

@JeffreyShallit Oh, eu vejo, bom ponto. É incrível (pelo menos para mim) se nada melhor do que ingênuo é conhecido por qualquer

fixo .

n

$n$

Lembik

Se alguém souber, talvez eles possam nos dizer.

Jeffrey Shallit

Sabe-se que o número de operações aritméticas necessário para calcular o determinante de um matriz é , onde é a constante multiplicação de matrizes. Veja, por exemplo, esta tabela na Wikipedia, bem como suas notas de rodapé e referências. Observe que a complexidade assintótica da inversão da matriz também é a mesma que a multiplicação da matriz no mesmo sentido. $n\times n$ $n^{\omega+o(1)}$ $\omega$

A equivalência é bastante eficaz. Em particular, você pode recursivamente calcular o determinante de uma matriz, trabalhando em blocos usando o complemento de Schur: $n\times n$ $(n/2) \times (n/2)$

D invertible ⟹ det (\begin{matrix} A & B \\ C & D \end{matrix}) = det (D) det (A - B D^{- 1} C) .

$\text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C).$

Assim, é possível calcular uma determinante calculando dois determinantes, invertendo uma matriz, multiplicando-se dois pares de matrizes e algumas operações mais simples. Expandindo as chamadas determinantes recursivamente, a complexidade acaba sendo dominada pela multiplicação e inversão da matriz. $n\times n$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$ $(n/2)\times (n/2)$

Isso funciona bem mesmo para pequenos e mesmo sem o uso de algoritmos de multiplicação de matriz sub-cúbica. (É claro que acaba sendo mais ou menos equivalente à eliminação gaussiana.) Por exemplo, para , podemos calcular com duas multiplicações, com quatro divisões, com multiplicações, $n$ $n=4$ $\det(D)$ $D^{-1}$ $BD^{-1}C$ $2\times 8=16$ $\det(A-BD^{-1}C)$ com duas multiplicações e a resposta final com uma multiplicação. O número total é multiplicações mais divisões, que é menor que os da expansão do cofator. O uso do algoritmo de Strassen salva duas multiplicações aqui, mas mais assintoticamente. $2+4+16+2+1=25$ $40$

Você pode perceber que essa expansão usa crucialmente a divisão. Se você deseja evitar a divisão, pode-se fazê-lo nas operações trabalhando com sequências Clow e programação dinâmica . É também ele conhecido como conseguir multiplicações e divisões não há. $O(n^4)$ $n^{2+\omega/2+o(1)}$

A. Rex
fonte

Você conhece algum limite inferior apenas no número de multiplicações? Mesmo para n = 3?

Jeffrey Shallit

O seu fraseado "o número de operações aritméticas necessário para calcular o determinante de um

matriz é

" sugere que um limite inferior é conhecido. Mas não vi isso em nenhum dos trabalhos citados. Estou esquecendo de algo?

n \times n

$n \times n$

n^{ω + o (1)}

$n^{\omega +o(1)}$

Jeffrey Shallit 30/11

O limite inferior está no artigo de W.Baur e V.Strassen "A complexidade das derivadas parciais" ( dx.doi.org/10.1016/0304-3975(83)90110-X )

Vladimir Lysikov

O número mínimo de operações aritméticas para calcular o determinante

Respostas: