linear equation - 演算法筆記

linear equation🚧

linear equation

特殊的矩陣有著特殊的演算法，降低時間複雜度。

(1) identity matrix
    copy and paste O(1)

⎡ 1 0 0 0 0 ⎤
⎢ 0 1 0 0 0 ⎥
⎢ 0 0 1 0 0 ⎥
⎢ 0 0 0 1 0 ⎥
⎣ 0 0 0 0 1 ⎦

(2) diagonal matrix
    element-wise scaling O(N)

⎡ 4 0 0 0 0 ⎤
⎢ 0 9 0 0 0 ⎥
⎢ 0 0 8 0 0 ⎥
⎢ 0 0 0 6 0 ⎥
⎣ 0 0 0 0 2 ⎦

(3) bidiagonal matrix / tridiagonal matrix
    Thomas's algorithm O(N)

⎡ 4 0 0 0 0 ⎤   ⎡ 4 2 0 0 0 ⎤
⎢ 3 9 0 0 0 ⎥   ⎢ 3 9 0 0 0 ⎥
⎢ 0 4 8 0 0 ⎥   ⎢ 0 4 8 2 0 ⎥
⎢ 0 0 3 6 0 ⎥   ⎢ 0 0 3 6 4 ⎥
⎣ 0 0 0 9 2 ⎦   ⎣ 0 0 0 9 2 ⎦

(4) triangular matrix
    forward/backward substitution O(N²)

⎡ 4 2 7 1 8 ⎤
⎢ 0 9 0 5 6 ⎥
⎢ 0 0 8 2 9 ⎥
⎢ 0 0 0 6 4 ⎥
⎣ 0 0 0 0 2 ⎦

(5) almost triangular matrix (Hessenberg matrix)
    LU decomposition O(N²)

⎡ 4 2 7 1 8 ⎤
⎢ 3 9 0 5 6 ⎥
⎢ 0 4 8 2 9 ⎥
⎢ 0 0 3 6 4 ⎥
⎣ 0 0 0 9 2 ⎦

(6) band matrix
    LU decomposition O(K²N)

⎡ 4 2 7 0 0 ⎤
⎢ 3 9 0 5 0 ⎥
⎢ 0 4 8 2 9 ⎥
⎢ 0 0 3 6 4 ⎥
⎣ 0 0 0 9 2 ⎦

(7) symmetric positive definite matrix
    Cholesky decomposition O(N³)

⎡ 9 1 2 1 0 ⎤
⎢ 1 8 1 2 1 ⎥
⎢ 2 1 9 1 2 ⎥
⎢ 1 2 1 8 1 ⎥
⎣ 0 1 2 1 9 ⎦

(8) diagonal-constant matrix (Toeplitz matrix)
    Levinson–Durbin algorithm O(N²)
    fast Fourier transform O(NlogN)

⎡ 5 9 8 0 6 ⎤
⎢ 2 5 9 8 0 ⎥
⎢ 1 2 5 9 8 ⎥
⎢ 4 1 2 5 9 ⎥
⎣ 3 4 1 2 5 ⎦

linear least squares

特殊的矩陣有著特殊的演算法，降低時間複雜度。

https://www.mathworks.com/help/matlab/math/iterativemethods.png
https://www.mathworks.com/help/matlab/math/iterative-methods-for-linear-systems.html

direct method vs. iterative method

古人將一次方程組演算法分成兩類：直接法、遞推法。前者得到精確解、後者得到近似解。

事實上，一次方程組演算法全部都是遞推法。例如高斯消去法是逐個橫條遞推、反覆調整矩陣。分類標題名不副實。分類標題應是函數遞推（反覆調整矩陣）、變數遞推（反覆調整解向量）。

直接法：

一、LU分解。例如高斯消去法、高斯喬登消去法、LU分解、Cholesky分解。

二、QR分解。例如Gram–Schmidt投影、Householder鏡射、Givens旋轉。

順帶一提，特徵分解、奇異值分解，也可以使用QR分解的三種基礎演算法。

遞推法：

一、鬆弛法。例如Jacobi's method、Gauss–Seidel method。

二、投影法。例如Kaczmarz's method。

三、最佳化演算法。例如Richardson's method、conjugate gradient method。

Toeplitz matrix🚧

Toeplitz matrix（constant-diagonal matrix）

「常對角矩陣」。每一條左上右下斜線是相同元素的矩陣。

⎡ 1 5 3 2 ⎤
⎢ 2 1 5 3 ⎥
⎢ 7 2 1 5 ⎥
⎣ 0 7 2 1 ⎦

演算法（Levinson–Durbin algorithm）

https://ocw.mit.edu/courses/6-341-discrete-time-signal-processing-fall-2005/06e8ddb9555ede1b094f5dc9d17ea254_lec13.pdf
https://hitonanode.github.io/cplib-cpp/linear_algebra_matrix/levinson.hpp.html