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

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

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.

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.

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

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

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.

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]

Simplex and Simulated Annealing are two very different beasts.

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

Jan Wassenberg suggested a great page:
http://lib-www.lanl.gov/numerical/bookcpdf.html

Really nice resource for numerical recipes.