Qual é o algoritmo mais rápido para calcular a matriz inversa e seu determinante para matrizes simétricas definidas positivas?

Dada uma matriz simétrica definida positiva, qual é o algoritmo mais rápido para calcular a matriz inversa e seu determinante? Para problemas em que estou interessado, a dimensão da matriz é 30 ou menos.

Alta precisão e velocidade são realmente necessárias. (milhões de matrizes são realizadas)
O determinante é necessário. Em cada cálculo, apenas um elemento da matriz iverse é necessário. Obrigado!

algorithms matrix Encomendas
fonte

Você precisa inverter milhões dessas matrizes? Caso contrário, a velocidade não deve ser um problema.

Wolfgang Bangerth

Editei seu título e sua pergunta para maior clareza. Se eu cometi algum erro, entre em contato.

Geoff Oxberry

@Wolfgang Bangerth Sim, a velocidade deve ser considerada.

Ordena

Você sabe qual elemento da matriz inversa é necessário? Ou pode ser uma entrada aleatória?

Memming

@ Ordens Seu comentário e edição parecem contraditórios: você precisa de um elemento do inverso, ou de todos eles?

Federico Poloni

Para problemas em que estou interessado, a dimensão da matriz é 30 ou menos.

Como observa WolfgangBangerth, a menos que você tenha um grande número dessas matrizes (milhões, bilhões), o desempenho da inversão da matriz normalmente não é um problema.

Dada uma matriz simétrica definida positiva, qual é o algoritmo mais rápido para calcular a matriz inversa e seu determinante?

Se a velocidade é um problema, você deve responder às seguintes perguntas:

Você realmente precisa de todo o inverso? (Muitos aplicativos não precisam formar um inverso explícito.)
Você realmente precisa do determinante? (Determinantes são incomuns, mas certamente não são desconhecidos na ciência da computação.)
Você precisa de alta precisão? (Os algoritmos de baixa precisão tendem a ser mais rápidos.)
Uma aproximação probabilística seria suficiente? (Os algoritmos probabilísticos tendem a ser mais rápidos.)

$A = LL^{T}$ $\det(A) = \prod_{i=1}^{n}l_{ii}^{2}$ $\det(A^{-1}) = \prod_{i=1}^{n}l_{ii}^{-2}$

Assumindo que é por , a decomposição de Cholesky pode ser calculada em torno de flops, que é cerca da metade do custo de uma decomposição de LU. No entanto, esse algoritmo não seria considerado "rápido". Uma decomposição aleatória da LU $A$ $n$ $n$ $n^{3}/3$ pode ser um algoritmo mais rápido que vale a pena considerar se (1) você realmente precisa fatorar um grande número de matrizes, (2) a fatoração é realmente a etapa limitante da sua aplicação e (3) qualquer erro incorrido no uso de um algoritmo aleatório é aceitável. Suas matrizes são provavelmente muito pequenas para que algoritmos esparsos valham a pena; portanto, as únicas outras oportunidades para algoritmos mais rápidos exigiriam estrutura matricial adicional (por exemplo, em faixas) ou exploração da estrutura de problemas (por exemplo, talvez você possa reestruturar seu algoritmo de maneira inteligente, para que você não é necessário calcular uma matriz inversa ou seu determinante). Algoritmos determinantes eficientes são aproximadamente o custo de resolver um sistema linear, dentro de um fator constante; portanto, os mesmos argumentos usados para sistemas lineares também se aplicam ao cálculo de determinantes.

Geoff Oxberry
fonte

Apenas uma breve nota: se , para calcular um único elemento deve-se calcular apenas o ésima coluna de . Uma vez calculada a fatoração de Cholesky, isso é feito por substituição direta e traseira em relação a um vetor rhs de todos os zeros e com apenas um único na linha . Como o cálculo pode ser interrompido assim que for calculado, o melhor caso é para pior caso para em que é necessário calcular a volta completa e substituições avançadas.

B = A^{- 1}

$B = A^{-1}$

b_{i j}

$b_{ij}$

j

$j$

B

$B$

j

$j$

b_{i j}

$b_{ij}$

b_{n n} = l_{n n}^{- 2}

$b_{nn} = l_{nn} ^{-2}$

b_{11}

$b_{11}$

Stefano M

@StefanoM Ainda melhor, você pode permutar sua matriz antes do início do cálculo para estar sempre na melhor das hipóteses.

Federico Poloni

Qual é o algoritmo mais rápido para calcular a matriz inversa e seu determinante para matrizes simétricas definidas positivas?

Respostas: