I have an equation of the form Ax = b, where x and b are dense vectors and A is a sparce, symmetric, and ''mostly'' tridiagonal matrix. I''ve read that such a system can be solved in nearly O(n) time (due to its sparsity) rather than O(n)^3 needed to solve such a system using Gaussian elimination. Unfortunately the article did not elaborate further. Does anyone know where I could find a tutorial on writting such an algorithm? Thanks in advance

I don''t have any good links, but google on "Jacobi Method", "Gauss Siedel", "Successive Overrelaxation". I think Mathworld has pseudocode for Successive Overrelaxation (SOR), which is an evolution of the Gauss Siedel method, which in turn is similar and usually a bit better than the Jacobi method. All are iterative methods of solving systems of equations that can converge more quickly than Gaussian Elimination.

Oh, I did find this presentation, which seems to be OK:

http://ceprofs.tamu.edu/jzhang/ch4n.ppt

Graham Rhodes
Principal Scientist
Applied Research Associates, Inc.

The above methods work for generalized sparse matrices. For tridiagonal systems specifically, there is a method called the Thomas Algorithm, if the system is diagonally dominant. There''s a brief discussion with details at this site:

Tridiagonal Matrix

Graham Rhodes
Principal Scientist
Applied Research Associates, Inc.

Cheers for the info. Its good to meet people willing to share the knowledge.