Имея трехдиагональную линейную систему SPD, можем ли мы предварительно вычислить, чтобы любые три индекса могли быть связаны за O (1) время?

Рассмотрим симметричную положительно определенную трехдиагональную линейную систему где и . Для трех индексов , если предположить , что выполняются только строки уравнения строго между и , мы можем исключить промежуточные переменные, чтобы получить уравнение вида

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$ где

. Это уравнение связывает значение

независимо от «внешнего» влияния (скажем, если было введено ограничение, влияющее на

v > 0

$v > 0$

x_{j}

$x_j$

x_{i}, x_{k}

$x_i,x_k$

x_{0}

$x_0$

Вопрос : Можно ли предварительно обработать линейную систему за время чтобы уравнение связи для любого можно было определить за время ? $Ax = b$ $O(n)$ $(i,j,k)$ $O(1)$

Если диагональ равна 2, отклонения от диагонали , а , то желаемый результат является аналитическим результатом для дискретизированного уравнения Пуассона. К сожалению, невозможно преобразовать общую трехдиагональную систему SPD в уравнение Пуассона с постоянными коэффициентами, не нарушая трехдиагональную структуру, в основном потому, что разные переменные могут иметь разные уровни «экранирования» (локально строгой положительной определенности). Например, простое диагональное масштабирование может устранить половину степеней свободы но не другую половину. $A$ $-1$ $b = 0$ $x$ $2n-1$ $A$

Интуитивно понятно, что решение этой проблемы потребовало бы организации проблемы таким образом, чтобы объем скрининга можно было накапливать в массив линейных размеров, а затем каким-то образом «отменять», чтобы получить уравнение связывания для данной тройки.

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

linear-algebra poisson Джеффри Ирвинг
источник

Ответы:

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

Джеффри Ирвинг
источник

Реализовав это, я могу подтвердить, что (1) он работает в точной арифметике и (2) он чрезвычайно нестабилен. Интуитивно понятно, что это решение выполняет экстраполяцию экспоненциальных функций, что нарушает хороший интерполяционный характер эллиптических задач.

Джеффри Ирвинг

b_{j} \approx 0

$b_j\approx 0$

n \log n

$n\log n$

O (n)

$O(n)$

O (\log n)

$O(\log n)$

Интересно, могли бы вы сделать что-то полезное с факторизацией циклическим редукцией A (которая, я считаю, все еще имеет размер O (n)), повторно используя столько блоков, которые остались бы неизменными при факторинге смежной главной подматрицы A. Я сомневаюсь это дает вам O (1), но, возможно, O (log n) ...

Роберт Бридсон
источник

O (\log n)

$O(\log n)$

У вас нет шансов на амортизацию?

Роберт Бридсон

Там происходит много другой амортизации, так что это вполне возможно. Я пока не знаю как.

Джеффри Ирвинг

Это то, что мне нужно, чтобы амортизировать стоимость: cstheory.stackexchange.com/questions/18655/… .

Джеффри Ирвинг

Большой! Кто-то опубликовал замечательное решение этого исторического вопроса, поэтому мне больше не нужен ответ на этот вопрос. Операция умножения полугрупп в этом вопросе исключает промежуточную переменную.

Джеффри Ирвинг

Вот еще одна попытка, которая более стабильна, чем метод отмены, но все же не очень хороша.

$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]: Джерард Меурант (1992), "Обзор обратной симметрической диагональной и блочной трехдиагональной матриц".

Джеффри Ирвинг
источник