Dado um sistema linear tridiagonal do SPD, podemos pré-calcular para que quaisquer três índices possam ser vinculados no tempo O (1)?

Considere um simétrica definida positiva tridiagonal sistema linear , onde e . Dados três índices , se assumirmos apenas linhas da equação estritamente entre e reter, podemos eliminar variáveis intermediárias para obter uma equação da forma

A x = b

$A x = b$

A \in R^{n \times n}

$A \in \mathbb{R}^{n \times n}$

b \in R^{n}

$b \in \mathbb{R}^n$

0 \leq i < j < k < n

$0 \le i < j < k < n$

i

$i$

k

$k$

u x_{i} + v x_{j} + w x_{k} = c

$u x_i + v x_j + w x_k = c$ onde

. Esta equação refere-se o valor de

independente da influência "fora" (dizer, se uma restrição que afectam

foi introduzido).

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$x_0$

Pergunta : É possível pré-processar o sistema linear no tempo para que a equação de ligação para qualquer possa ser determinada no tempo ? $Ax = b$ $O(n)$ $(i,j,k)$ $O(1)$

Se a diagonal de for 2, os offdiagonals são , e , o resultado desejado é o resultado analítico para a equação de Poisson discretizado. Infelizmente, não é possível transformar um sistema tridiagonal geral do SPD em uma equação de Poisson de coeficiente constante sem quebrar a estrutura tridiagonal, essencialmente porque variáveis diferentes podem ter diferentes níveis de "triagem" (definição positiva localmente estrita). Um simples dimensionamento diagonal de , por exemplo, pode eliminar metade dos DOFs de mas não a outra metade. $A$ $-1$ $b = 0$ $x$ $2n-1$ $A$

Intuitivamente, uma solução para esse problema exigiria a organização do problema para que a quantidade de triagem pudesse ser acumulada em uma matriz de tamanho linear e, de alguma forma, "cancelada" para chegar à equação de ligação para o triplo dado.

Atualização (mais intuição) : Em termos de PDEs, tenho um problema elíptico linear discretizado em 1D e quero saber se posso gastar em pré-computação para produzir algum tipo de solução "analítica" que possa ser pesquisada no tempo , onde posso variar onde estão as condições de contorno. $O(n)$ $O(1)$

linear-algebra poisson Geoffrey Irving
fonte

Respostas:

Aqui está uma solução um tanto instável que só funciona quando o acoplamento entre variáveis é sempre não-regenerado. Suponha, por simplicidade, que . Primeiro, pré-calcule as equações de ligação para para , digamos $b = 0$ $n$ $(0,i,n-1)$ $0 \le i < n$

x_{i} = a_{i} x_{0} + b_{i} x_{n - 1}

$x_i = a_i x_0 + b_i x_{n-1}$

Agora, dado , podemos combinar as equações de ligação e th e eliminar para obter $i < j$ $i$ $j$ $x_{n-1}$

\begin{aligned} b_{j} x_{i} & = a_{i} b_{j} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{i} x_{j} & = a_{j} b_{i} x_{0} + b_{i} b_{j} x_{n - 1} \\ b_{j} x_{i} - b_{i} x_{j} & = (a_{i} b_{j} - a_{j} b_{i}) x_{0} \\ x_{i} & = \frac{a_{i} b_{j} - a_{j} b_{i}}{b_{j}} x_{0} + \frac{b_{i}}{b_{j}} x_{j} \end{aligned}

$\begin{aligned} b_j x_i &= a_i b_j x_0 + b_i b_j x_{n-1} \\ b_i x_j &= a_j b_i x_0 + b_i b_j x_{n-1} \\ b_j x_i - b_i x_j &= (a_i b_j - a_j b_i) x_0 \\ x_i &= \frac{a_i b_j - a_j b_i}{b_j} x_0 + \frac{b_i}{b_j} x_j \end{aligned}$

Este processo pode ser repetido mais uma vez para eliminar dado . Infelizmente, perdemos estabilidade perto de , ou em geral se o sistema tridiagonal se dissociar em blocos independentes. Se isso não é problema, mas estou preocupado com a quebra de valores pequenos, mas positivos. $x_0$ $(i,j,k)$ $b_j = 0$ $b_j = 0$

Geoffrey Irving
fonte

Tendo implementado isso, posso confirmar que (1) funciona em aritmética exata e (2) é extremamente instável. Intuitivamente, essa solução faz várias extrapolações de funções exponenciais, o que quebra o bom caráter interpolatório dos problemas elípticos.

Geoffrey Irving

b_{j} \approx 0

$b_j\approx 0$

n \log n

$n\log n$

O (n)

$O(n)$

O (\log n)

$O(\log n)$

Gostaria de saber se você poderia fazer algo útil com uma fatoração de redução cíclica de A (que eu acredito que ainda é tamanho O (n)), reutilizando tantos blocos que permaneceriam inalterados ao calcular uma submatriz principal contígua de A. Duvido fornece O (1), mas talvez O (log n) ...

Robert Bridson
fonte

O (\log n)

$O(\log n)$

Sem chance de amortização ajudando você?

Robert Bridson

Há muitas outras amortizações em andamento, então é bem possível. Eu não sei ainda, no entanto.

Geoffrey Irving

É isso que eu precisaria para amortizar o custo: cstheory.stackexchange.com/questions/18655/… .

Geoffrey Irving

Ótimo! Alguém postou uma solução maravilhosa para essa questão histórica, então não preciso mais da resposta para essa pergunta. A operação de multiplicação de semigrupos nessa pergunta está eliminando uma variável intermediária.

Geoffrey Irving

Aqui está outra tentativa, mais estável que o método de cancelamento, mas ainda não muito boa.

$A$ $B = A^{-1}$

B_{i j} = b_{i + 1} \dots b_{j} \frac{d_{j + 1} \dots d_{n}}{δ_{i} \dots δ_{n}}

$B_{ij} = b_{i+1}\cdots b_j \frac{d_{j+1}\cdots d_n}{\delta_i \cdots \delta_n}$

$i \le j$ $b_i$ $d_i,\delta_i$ $UL$ $LU$ $A$ $i < j < k$

x_{j} = {(\begin{matrix} B_{j i} \\ B_{k i} \end{matrix})}^{T} {(\begin{array}{cc} B_{i i} & B_{i k} \\ B_{k i} & B_{k k} \end{array})}^{- 1} (\begin{matrix} x_{i} \\ x_{k} \end{matrix})

$x_j = \left(\begin{array}{c}B_{ji} \\ B_{ki}\end{array}\right)^T \left(\begin{array}{cc}B_{ii} & B_{ik} \\ B_{ki} & B_{kk}\end{array}\right)^{-1} \left(\begin{array}{c}x_i \\ x_k\end{array}\right)$

$i$ $k$ $i$ $k$ $2 \times 2$

[1]: Gerard Meurant (1992), "Uma revisão sobre o inverso de matrizes diagonais simétricas e tridiagonais de blocos".

Geoffrey Irving
fonte