Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Motorherp

Sparse matricies

This topic is 5219 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!