Tridiagonal sparse matrix - linear equation

Question

I have to following linear system to solve : $Ax=e_1$ where $A$ is a sparse tridiagonal matrix with the main diagonal terms $a_{ii}$ being all different, and the off-diagonal terms being each others complex conjugate ($\bar{b_{ij}} = b_{ji}$). $e_1$ is the unit vector $(1, 0, 0, ..., 0)$. How would you proceed to do this efficiently, knowing that my matrices and vectors contain million of elements? I'd be firstly interested in the mathematical way to do it, so I can find some inspiration to implement it myself. And secondly (if it is the right site to ask this), if you know of any implementation in FORTRAN for this kind of problem? Googling it brings me to packages such as LAPACK, but it is stated explicitly it is not optimized for general sparse matrices. And seeing the number of elements, an $O(n)$ method would be highly appreciated.

Oh, so you want the first column of the inverse of a Hermitian tridiagonal matrix? Usual methods for solving general tridiagonal systems are already $O(n)$ in effort to begin with... — J. M. ain't a mathematician, Apr 19 '11 at 10:08
Yes, Hermitian :) And which are these usual methods? I've one using continued fractions, but it only works to find the first element of x. — Nigu, Apr 19 '11 at 10:12
If the tridiagonal matrix is positive definite, the second routine I linked to is what you need. — J. M. ain't a mathematician, Apr 19 '11 at 10:12
It is true that you can express the entries of the inverse of a tridiagonal matrix as CFs... but anyway, you'd want to verify first that your matrix is positive definite or diagonally dominant at the very least. Where did your tridiagonals come from? — J. M. ain't a mathematician, Apr 19 '11 at 10:15

Tridiagonal sparse matrix - linear equation

0 Answers0