Maneira mais rápida de resolver um sistema de equações lineares

8

Eu tenho que resolver um sistema de até 10000 equações com 10000 incógnitas o mais rápido possível (de preferência em alguns segundos). Eu sei que a eliminação gaussiana é muito lenta para isso, então qual algoritmo é adequado para esta tarefa?

Todos os coeficientes e constantes são números inteiros não negativos módulo p (onde p é primo). É garantido que haja apenas 1 solução. Eu preciso da solução módulo p.

algorithms linear-algebra matrices numerical-algorithms tmwilliamlin168
fonte

Respostas:

10

Uma decomposição LU de umn×n matriz pode ser calculada em O(M(n)) hora, onde M(n) é a hora de multiplicar dois n×nmatrizes. Portanto, você pode encontrar uma solução para um sistema den equações lineares em n incógnitas em O(M(n))Tempo. Por exemplo, o algoritmo de Strassen alcançaM(n)=O(n2.8), que é mais rápido que a eliminação gaussiana. Consulte https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion .

Em vez de tentar implementar isso sozinho, eu sugeriria o uso de uma biblioteca: por exemplo, uma biblioteca BLAS.

DW
fonte
Reduza também o módulo p no final do cálculo.
Fade2black
2
@ fade2black, na verdade, provavelmente será muito melhor usar uma implementação projetada para uso com aritmética mod p (isto é, reduzir o mod p em cada etapa, não apenas no final).
DW
Caso o link da Wikipedia seja alterado, a referência fornecida lá para o O(M(n))o resultado pode ser encontrado, por exemplo, na seção 28.2 da 3ª edição de Cormen et al, Introdução aos algoritmos . Especificamente, eles mostram a "equivalência algorítmica" entre multiplicação e inversão de matriz. Mas, presumivelmente, é possível vincular a inversão da matriz e a decomposição da LU.
Chill2Macht 19/02
4

Existe o que você deseja alcançar, existe realidade e, às vezes, eles estão em conflito. Primeiro, verifique se o seu problema é um caso especial que pode ser resolvido mais rapidamente, por exemplo, uma matriz esparsa. Então você procura algoritmos mais rápidos; A decomposição da LU terminará um pouco mais rápida. Em seguida, você investiga o que Strassen pode fazer por você (o que não é muito; pode economizar 1/2 das operações se você multiplicar o tamanho do problema por 32).

E então você usa força bruta. Use um sistema multiprocessador com vários threads. Use unidades vetoriais disponíveis. Organize seus dados e operações para serem compatíveis com o cache. Investigue qual é a maneira mais rápida de fazer cálculos no módulo p para alguns p fixos. E você pode salvar operações com frequência, não realizando as operações módulo p (resultado no intervalo 0 ≤ resultado <p), mas um pouco mais relaxado (por exemplo, resultado no intervalo -p <resultado <p).

gnasher729
fonte
2

A melhor maneira de resolver grandes equações lineares é usar paralelização ou, de alguma forma, distribuir cálculos entre CPUs ou algo assim.

Consulte CUDA, OpenCL, OpenMP.

Muitas pessoas sugerem, Strassen's algorithmmas ela tem uma constante oculta muito grande, o que a torna ineficiente.

A propósito: suas equações lineares podem ser muito esparsas (muitos zeros), existem poucas otimizações muito claras para resolvê-las em paralelo.

Oleg Kovalov
fonte
O tamanho da matriz é 10.000 por 10.000, por isso suponho que Strassen possa salvar alguma coisa. Apenas não muito.
precisa saber é o seguinte
1
@ gnasher729 Eu tenho algumas dúvidas, Alex Stapanov, em uma de suas palestras, é mencionado que Boing estava usando o algoritmo de Strassen para matrizes realmente grandes (1Mx1M caso) e eles estavam descontentes com o desempenho. Mas acho que essas informações estão desatualizadas para o hardware moderno.
Oleg Kovalov