# S.O.S. Mathematics CyberBoard

Your Resource for mathematics help on the web!
 It is currently Sat, 18 May 2013 12:12:26 UTC

 All times are UTC [ DST ]

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Linear & sparse simultaneous equation algorithmsPosted: Sun, 27 Mar 2011 05:39:21 UTC
 S.O.S. Newbie

Joined: Sun, 27 Mar 2011 05:00:52 UTC
Posts: 4
I'm dealing with large, sparse simultaneous equation matrices and am looking for the fastest algorithm to solve for the unknowns.

By large I mean the coefficient matrix is in the range of 50x50 up to 200x200.
By sparse I mean that as much as 98% of the coefficient matrix is zero.
The coefficient matrix is sometimes symmetric and sometimes not.

I've been using two algorithms; gaussian elimination, and crouts method with LU decomposition. There's no clear winner for speed between them, with the fastest decided on a matrix by matrix basis. Neither is as fast as I want (by a LOT), so I'm looking for alternatives.

Neither method uses the sparsity of the coefficient matrix in its algorithm, so that's something that looks like it could help speed the solution. I know there are sparse-matrix techniques and have started reading about them, but so far they look aimed more at reducing memory requirements (to store MASSIVE matrices) than to speed up the solution, though I'm still trying to get my head around them. Memory usage isn't a concern for me. I'll keep reading about this stuff, but if there's a particular method that sounds suited to my needs I'd love to hear about it.

I also wondered if the matrix could be simplified or optimized, to reduce its size. I haven't found anything that sounds worth trying yet.

I'm coming at this problem from a programming point of view, rather than a mathematical one. I'm more likely to understand an algorithm than a formula.

Any thoughts or nudges in the right direction appreciated.

Top

 Post subject: Re: Linear & sparse simultaneous equation algorithmsPosted: Sun, 27 Mar 2011 06:37:15 UTC
 Moderator

Joined: Mon, 29 Dec 2008 17:49:32 UTC
Posts: 6001
Location: 127.0.0.1, ::1 (avatar courtesy of UDN)
Zuma wrote:
I'm dealing with large, sparse simultaneous equation matrices and am looking for the fastest algorithm to solve for the unknowns.

By large I mean the coefficient matrix is in the range of 50x50 up to 200x200.
By sparse I mean that as much as 98% of the coefficient matrix is zero.
The coefficient matrix is sometimes symmetric and sometimes not.

I've been using two algorithms; gaussian elimination, and crouts method with LU decomposition. There's no clear winner for speed between them, with the fastest decided on a matrix by matrix basis. Neither is as fast as I want (by a LOT), so I'm looking for alternatives.

Neither method uses the sparsity of the coefficient matrix in its algorithm, so that's something that looks like it could help speed the solution. I know there are sparse-matrix techniques and have started reading about them, but so far they look aimed more at reducing memory requirements (to store MASSIVE matrices) than to speed up the solution, though I'm still trying to get my head around them. Memory usage isn't a concern for me. I'll keep reading about this stuff, but if there's a particular method that sounds suited to my needs I'd love to hear about it.

I also wondered if the matrix could be simplified or optimized, to reduce its size. I haven't found anything that sounds worth trying yet.

I'm coming at this problem from a programming point of view, rather than a mathematical one. I'm more likely to understand an algorithm than a formula.

Any thoughts or nudges in the right direction appreciated.

Why not use an iterative approach, for example, Gauss-Seidel or SOR?

_________________

Top

 Post subject: Re: Linear & sparse simultaneous equation algorithmsPosted: Mon, 28 Mar 2011 07:37:13 UTC
 S.O.S. Newbie

Joined: Sun, 27 Mar 2011 05:00:52 UTC
Posts: 4
outermeasure wrote:
Why not use an iterative approach, for example, Gauss-Seidel or SOR?

Thanks very much for the suggestions. I've read some stuff about SOR and it looks like it might be ideal. Just the nudge I was hoping for.

Thanks again.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

 All times are UTC [ DST ]

#### Who is online

Users browsing this forum: No registered users

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ High School and College Mathematics    Algebra    Geometry and Trigonometry    Calculus    Matrix Algebra    Differential Equations    Probability and Statistics    Proposed Problems Applications    Physics, Chemistry, Engineering, etc.    Computer Science    Math for Business and Economics Advanced Mathematics    Foundations    Algebra and Number Theory    Analysis and Topology    Applied Mathematics    Other Topics in Advanced Mathematics Other Topics    Administrator Announcements    Comments and Suggestions for S.O.S. Math    Posting Math Formulas with LaTeX    Miscellaneous