2
$\begingroup$

Doing LU decomposition of tri-diagonal matrix and then solving the eqn by using forward substitution followed by backward substitution is done is O(n) time. http://www.cfm.brown.edu/people/gk/chap6/node13.html

But what are the number of operations and the time complexity of LUP decomposition of tri-diagonal matrix?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

LU factorization with partial pivoting for banded matrices of size $n\times n$ with bandwidth $w$ (number of subdiagonals plus number of superdiagonals) requires $O(w^2n)$ flops, triangular solvers require $O(wn)$ flops.

Thus, solving linear equations with tridiagonal matrix using LU factorization with partial pivoting also can be done in $O(n)$ floating point operations.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .