   Sparse matricies
  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 RhodesPrincipal ScientistApplied 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 RhodesPrincipal ScientistApplied Research Associates, Inc. ;  Cheers for the info. Its good to meet people willing to share the knowledge. 