¿Cómo resuelve LAPACK los sistemas tridiagonales y por qué?

9

En mi proyecto, tengo que resolver un par de matrices tridiagonales en cada paso, por lo que es crucial tener un buen solucionador para esos. Hice mi propia implementación, solo la forma clásica de hacerlo descrita en Wikipedia. Luego intenté usar Lapack, ¡y para mi sorpresa fue más lento!

Ahora, dentro de Lapack parece que resuelve por factorización LU y me pregunto por qué, ¿no es más complejo de lo que podría ser?

Además, encontré un algoritmo en el libro "Recetas numéricas" de nr.com que divide recursivamente el sistema en problemas tridiagonales más pequeños. Parecía prometedor. ¿Hay alguna otra cosa por ahí?

Actualización: el tamaño del problema es de aproximadamente 1000x1000. Usé GotoBLAS, también te da una biblioteca Lapack 3.1.1. El problema no es simétrico. Usé la rutina Lapack para matrices tridiagonales generales.

banded-matrix lapack tiam
fuente
2
Deberá indicar qué rutinas de LAPACK utilizó para esto. Tenga en cuenta que dgtsv realiza un giro parcial, pero su código puede no hacerlo. Indique también con qué implementación de LAPACK probó y con qué tamaños de problemas comparó. Además, ¿su problema es simétrico positivo definido?
Jed Brown
Agregué información en la formulación de la pregunta.
tiam
¿Su aplicación tiene algo que ver con los métodos de volumen finito?
Investigación
Es diferencias finitas, pero en esta perspectiva es más o menos lo mismo, supongo.
tiam

Respuestas:

6

Está utilizando una implementación de referencia que hace pivote parcial. Las soluciones tridiagonales hacen muy poco trabajo y no requieren BLAS. Es probable que sea más lento que su código porque hace pivote parcial. El código fuente de dgtsv es sencillo.

Si va a resolver con la misma matriz varias veces, es posible que desee almacenar los factores utilizando dgttrf y dgttrs . Es posible que las implementaciones en un LAPACK optimizado como MKL, ACML o ESSL sean más efectivas.

Jed Brown
fuente
Tengo un poco de curiosidad Gaussian Elim con PP funcionaría para todas las matrices, incluida TriDiagonal. En CFD, utilizamos un método especial para casos de FVM 1D llamado TDMA . ¿Cuál crees que sería más rápido para el caso que está discutiendo? Aunque, no estoy completamente seguro de que sus matrices sean diagonalmente dominantes.
Investigación
El TDMA es lo que implementé en mi código. La pregunta es por qué la Lapack superrápida usaría el procedimiento de pivote parcial en una matriz tan particular, que se resuelve más rápido con un método tan fácil como TDMA.
tiam
Es exactamente el mismo algoritmo (eliminación gaussiana especializada para una matriz tridiagonal), pero su implementación no hace pivote parcial, por lo que puede ser numéricamente inestable. Ese pivote no es gratuito y se compara con la implementación de referencia. La implementación de referencia no está optimizada para el rendimiento y el pivote parcial no es gratuito.
Jed Brown
Entiendo lo que quieres decir, obtengo ventaja de mi conocimiento sobre los sistemas que estoy resolviendo. ¿Otras implementaciones de LAPACK aumentan el rendimiento debido a la adaptación a una arquitectura específica o va más allá de eso?
tiam