Jump to content
  • Advertisement

Archived

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

EPHERE

Systems of equations

This topic is 5800 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

In my code am trying to implement constrained minimization and optimization functions. To do this I need some way of computing two big systems of equations and this is where I am stuck I am wondering if there are any robust alghorithms/libraries for visual c++ that deal with solutions to linear systems of equations. I have searched the net and cannot find any that are reasonable. There are some, for example that are imported from Fortran, but they are either expensive or too complicated. Are there any tutorials/articles on alghorithms that solve systems of equations? Any help is greatly appreciated. Regards, EPHERE

Share this post


Link to post
Share on other sites
Advertisement
well you could try it with the gaussian elemination method.
this is a really easy way to solve eq. systems by hand but since it''s somewhat algorithmically defined it isn''t that hard to implement in code.

http://www.math.hmc.edu/calculus/tutorials/linearsystems/" this propably describes it better then i could (near the bottom there are the 5 steps of the algorithm to get the matrix into row-echelon form.
After that you just work your way up from the last row, insert value of that variable into second-from last row, then both into 3rd from last row etc. until you got them all.
the problem when letting a computer do it is the repeated 1/x which introduces some error, but it shouldn''t be too bad.









Runicsoft -- home of my open source Function Parser and more

Share this post


Link to post
Share on other sites
I''m guessing this is not game development related, specifically. However, I''ll allow the post since AI and pathfinding, among other things, are very much constrained optimization problems that occur in game development.

I''ve done quite a bit of optimization work, including constrained optimization. Mostly in the engineering world. It can be a hard problem to solve.

As for solving large systems of linear equations, you can''t get any easier than the Jacobi or Guass-Siedel iterative methods. A minor enhancement gives you successive overrelaxation (SOR). These methods are subject to stability bounds, but they are quite amazingly easy to implement. A search on google for those method names may help you find something. If you have exactly a tridiagonal matrix (which often occur in numerical solutions to 2D field problems, such 2D fluid dynamics for subsonic flow) then you could use the very clever "Thomas" algorithm to solve it. A pentadiagonal matrix (which often occur in solutions to 3D field problems) might also have a clever solution. But for general methods, Jacobi, GS, and SOR are a great start for easy implementation.

Sorry, but I''m massively busy at work right now, and will be for the next few weeks. Don''t have time to do full justice and reply with implementation details.

I don''t have any specific links to give you either, but a good place to look for technical docs is Citeseer:

http://citeseer.nj.nec.com/cs

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Just a couple of comments on the Gaussian elimination method.....

As Burning_Ice mentioned, it is fairly easy to implement, though in my opinion not as easy as Jacobi, etc.

GE works very well to a point . Once the number of equations gets large, roundoff error kills you with this method, while the iterative methods can keep roundoff under control even for very large systems. Up to perhaps 100 equations, double-precision GE should probably work fine for *most*, *well-behaved* (read diagonal dominate) systems.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Thanks grhodes and Burning_Ice. That is all the info that I need to get me started. Another person also suggested using simplex method to solve constrained minimization/maximization.

GE is the first method I would use to solve linear equations with pen and paper. I always thought, however, that it is not feasable to implement it as a computer alghorithm.
I will try Jacobi, GS, and SOR methods.

Thanks again guys.

EPHERE

Share this post


Link to post
Share on other sites
Just a question- When you say optimization, are you talking about linear programming optimization? I have done some Gaussian elimination before and have found it to be very good for what I have done. I love this math stuff, should do more research on it, but my AP English class kinda boggs me down Time to finish writing that Sophocles essay that I never got to over Thanksgiving break.
Brendan

Share this post


Link to post
Share on other sites
By "simplex method" do you mean simulated annealing? If so, that is usually the second last resort where no other algorithms are available.

All the algorithms mentioned above are good. AS another reference try lapack (more specifically clapack) for good implementations.

Share this post


Link to post
Share on other sites
Simplex and Simulated Annealing are two very different beasts.

The simplex method considers a triangular patch on the surface to be optimised. Find the two vertices with the lowest/highest values and flip the triangle along the edge defined by those two vertices. Keep track of which triangles you have passed through. Stop the algorithm if you find an oscillation and read off the highest valued vertex.

Cheers,

Timkin

[edited by - Timkin on December 3, 2002 1:36:12 AM]

Share this post


Link to post
Share on other sites
Simplex and Simulated Annealing are two very different beasts.

Not if you are using the downhill simplex version of simulated annealing for continuous spaces.

Share this post


Link to post
Share on other sites
Jan Wassenberg suggested a great page:
http://lib-www.lanl.gov/numerical/bookcpdf.html

Really nice resource for numerical recipes.

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!