Solve Ax = b tridiagonal matrix

#1

I’m trying to solve Ax = b in matrix.

using ToeplitzMatrices
function toeplitz(n)
    r = [4; -1; zeros(n-2)]
    Toeplitz(r, r)
end

and I’m using this function to generate matrix with n [10,100,200,300,400] and try to solve Ax = b (Cholesky factorization)
I found that probably I can use LDL factorization

for a in [10, 100,200,300,400]
    A = toeplitz(a)
    LDLT = ldl(A)
    x = LDLT \b
end

and gave it `UndefVarError: ldl not defined

Stacktrace:
[1] top-level scope at .\In[34]:3`

I’m not sure what I should change. Or maybe it’s not a good way to resolve this and there is another way ?

0 Likes

#2

Are you looking for

help?> ldlt
search: ldlt ldlt! LDLt foldl mapfoldl

  ldlt(S::SymTridiagonal) -> LDLt

  Compute an LDLt factorization of the real symmetric tridiagonal matrix S such that S =
  L*Diagonal(d)*L' where L is a unit lower triangular matrix and d is a vector. The main use of an
  LDLt factorization F = ldlt(S) is to solve the linear system of equations Sx = b with F\b.

in the LinearAlgebra module?

1 Like

#3

Since the matrix is symmetric tridiagonal, you should take advantage of that by constructing the SymTridiagonal type, which has only O(n) storage and can be solved in O(n) time:

mymatrix(n) = SymTridiagonal(fill(4, n), fill(-1, n-1))

If you just do mymatrix(n) \ b, it automatically uses the LDLᵀ factorization, which for a tridiagonal matrix takes O(n) time.

5 Likes