O algoritmo de Thomas é a maneira mais rápida de resolver um sistema linear tridiagonal esparso, diagonalmente dominante, simétrico

Eu estou querendo saber se o algoritmo Thomas é a maneira mais rápida (provàvelmente?) De resolver um sistema tridiagonal esparso com dominação diagonal simétrica em termos de complexidade algorítmica (sem procurar pacotes de implementação como LAPACK etc.). Eu sei que o algoritmo Thomas e o multigrid são de complexidade , mas talvez o fator constante para o multigrid seja menor? Não me parece que o multigrid possa ser mais rápido, mas não sou positivo.$O(n)$

Nota: Estou considerando o caso em que as matrizes são muito grandes. Métodos diretos ou iterativos são aceitáveis.

Acredito que comparar um método iterativo (multigrid) com um método direto / exato (Thomas) em termos de contagem exata de operações não é realmente significativo. O IIRC, a contagem de operações da Thomas é de para qualquer sistema tridiagonal. A única vez em que consigo imaginar uma batida multigrelha concebível é para um caso trivial de ter uma solução linear, e mesmo assim o custo de avaliar o residual em cada nível seria comparável ao custo de Thomas.$8N$

A utilidade do multigrid está no fato de ser geral para matrizes esparsas e não restrita a sistemas tridiagonais.$O(N)$

A resposta curta é que o algoritmo Thomas será mais rápido do que qualquer esquema iterativo para quase todos os casos. A exceção talvez seja a aplicação de uma única iteração de um esquema iterativo muito simples, como Gauss-Seidel, mas é altamente improvável que isso dê uma solução aceitável. Além disso, isso está ignorando as preocupações de processamento paralelo.

$\mathcal O(n)$$\mathcal O(n)$

$5N$$3N$$3N-2$$2N-2$

Os loops multigrid mesmo no núcleo único são vetorizáveis ​​pelo otimizador. Portanto, embora a contagem de operações possa ajudar, não devemos esquecer que, mesmo no mundo serial, os processadores possuem paralelismo de vetores e, portanto, o tempo de solução pode não ser exatamente o que previmos na análise de custos.