Dado un sistema lineal tridiagonal SPD, ¿podemos calcular previamente para que se puedan vincular tres índices en el tiempo O (1)?

Considere una simétrica definida positiva tridiagonal sistema lineal , donde y . Dados tres índices , si asumimos que solo las filas de ecuaciones estrictamente entre y mantienen, podemos eliminar variables intermedias para obtener una ecuación de la 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$ donde

. Esta ecuación relaciona el valor de

con

independientemente de la influencia "externa" (por ejemplo, si se introdujo una restricción que afecta a

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$x_0$

Pregunta : ¿Es posible preprocesar el sistema lineal en el tiempo para que la ecuación de enlace para cualquier se pueda determinar en el tiempo ? $Ax = b$ $O(n)$ $(i,j,k)$ $O(1)$

Si la diagonal de es 2, los offdiagonals son , y , el resultado deseado es el resultado analítico para la ecuación de Poisson discretizado. Desafortunadamente, no es posible transformar un sistema tridiagonal SPD general en una ecuación de Poisson de coeficiente constante sin romper la estructura tridiagonal, esencialmente porque las diferentes variables pueden tener diferentes niveles de "detección" (definición positiva local estricta). Una escala diagonal simple de , por ejemplo, puede eliminar la mitad de los DOF de pero no la otra mitad. $A$ $-1$ $b = 0$ $x$ $2n-1$ $A$

Intuitivamente, una solución a este problema requeriría organizar el problema para que la cantidad de detección se pueda acumular en una matriz de tamaño lineal y luego de alguna manera "cancelarse" para llegar a la ecuación de enlace para el triple dado.

$O(n)$ $O(1)$

linear-algebra poisson Geoffrey Irving
fuente

Respuestas:

$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}$

$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}$

$x_0$ $(i,j,k)$ $b_j = 0$ $b_j = 0$

Geoffrey Irving
fuente

Una vez implementado esto, puedo confirmar que (1) funciona en aritmética exacta y (2) es extremadamente inestable. Intuitivamente, esta solución hace un montón de extrapolación de funciones exponenciales, lo que rompe el buen carácter interpolatorio de los 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)$

Me pregunto si podría hacer algo útil con una factorización de reducción cíclica de A (que creo que todavía es del tamaño O (n)), reutilizando la mayor parte de los bloques que permanecerían sin cambios al factorizar una submatriz principal contigua de A. Dudo te da O (1), pero tal vez O (log n) ...

Robert Bridson
fuente

O (\log n)

$O(\log n)$

¿No hay posibilidad de que la amortización te ayude?

Robert Bridson

Hay muchas otras amortizaciones en marcha, por lo que es bastante posible. Sin embargo, todavía no sé cómo.

Geoffrey Irving

Esto es lo que necesitaría para amortizar el costo: cstheory.stackexchange.com/questions/18655/… .

Geoffrey Irving

¡Excelente! Alguien publicó una solución maravillosa para esa pregunta teórica, por lo que ya no debería necesitar la respuesta a esta pregunta. La operación de multiplicación de semigrupo en esa pregunta está eliminando una variable intermedia.

Geoffrey Irving

Aquí hay otro intento, que es más estable que el método de cancelación pero que aún no es muy bueno.

$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), "Una revisión sobre el inverso de la diagonal simétrica y las matrices de bloques tridiagonales".

Geoffrey Irving
fuente