Implementação eficiente de algoritmo de matriz tridiagonal

12

Estou resolvendo um problema físico usando esquema numérico implícito. Isso me leva a resolver uma equação linear com matriz tridiagonal. Eu codifiquei esse algoritmo da Wikipedia. Gostaria de saber se existe uma biblioteca eficiente que permita resolver esse tipo de equação de maneira otimizada. Uma observação importante é que a própria matriz muda apenas quando os parâmetros do sistema estão sendo alterados, por isso tive a oportunidade de pré-calcular algumas etapas do algoritmo para obter um bom bônus de desempenho. Eu estou usando C ++.

linear-algebra libraries c++ gmk
fonte
Qual o tamanho de um sistema, ele precisa ser paralelo?
aterrel 30/11
1
O tamanho depende da precisão necessária (valores de centenas a dezenas de milhares). Agora estou codificando em um computador, mas é possível obter acesso ao supercomputador da universidade com muitos cpus disponíveis, portanto, o suporte ao paralelismo seria bom.
Gmk

Respostas:

15

Você provavelmente deveria começar com a implementação do LAPACK,? Gtsv, por exemplo, dgtsv . Se você deseja uma versão com memória distribuída, pode começar com o p? Gtsv do ScaLAPACK.

EDIT: Como sua matriz não muda com muita frequência, você pode evitar fatorar redundantemente a matriz tridiagonal dividindo a rotina LAPACK? Gtsv na etapa de fatoração,? Gttrf, e o estágio de resolução,? Gttrs. Rotinas nomeadas da mesma forma existem no ScaLAPACK que atendem ao mesmo propósito.

Jack Poulson
fonte
Obrigado, parece que eu preciso. Vou tentar agora executar essas rotinas do meu código.
Gmk
1
Como você está chamando de C ++, certifique-se de declarar o protótipo dentro de um bloco externo "C" {}. Dependendo do seu sistema, pode ser necessário anexar um sublinhado ao nome da rotina.
Jack Poulson
2

Para sistemas paralelos distribuídos : eu não experimentei o ScaLAPACK, que possui um solucionador tridiagonal paralelo, para o qual existem exemplos disponíveis online . Tentei com algum sucesso um método proposto por David Moulton em uma publicação da LANL . Codificar isso pode ser mais do que você deseja fazer, mas usando o LAPACK, é um passo em frente.

Yann
fonte
1

Encontrei um algoritmo recursivo interessante aqui na página 975. Parece promissor, eu me pergunto o que as pessoas mais experientes dizem sobre isso.

tiam
fonte
Receitas numéricas tem alguns erros. Em termos de uma fonte de códigos a ser usada, não é a melhor, embora alguns a considerem um clássico. Eu ficaria surpreso se o ScaLAPACK não implementasse um algoritmo pelo menos tão eficiente quanto a redução cíclica recursiva.
Geoff Oxberry