# System of Lin. Eqations, resulting from a weighted graph. How to solve this numerically?

We have a problem that leads to a system of linear eqations which has to be solved numerically. Unfortunately, we don't know a convenient way to do that. Still, since our problem seems to be a common one, we believe that there are algorithms specially designed for it.

Do you know a fitting algorithm? Do you know an implementation in c++? That would help us a lot!

http://pdfcast.org/pdf/linalgproblem (Document has three pages)

PS: I'm afraid this question may be inappropriate for MathOverflow. If so, I'm sorry. I didn't want to bother anybody.

-
Dear Konstantin, did you happen to get a chance to read the FAQ for Mathoverflow? Maybe on math.SE you'll get more response to this question. – Suvrit Aug 28 '11 at 22:51
You're right, I'm a undergraduate in physics, and as I heard now, you only accept math-graduates here. Please leave my question this time, but in the near future, I will rather join math.SE. (I posted this question there, too, but didn't get any answer yet.) – Konstantin Schubert Aug 31 '11 at 11:26

The answer depends on what properties your system of equations has. Is the coefficient matrix symmetric positive definite? Symmetric indefinite? Not symmetric? Is the coefficient matrix sparse?

Trefethen's book Numerical Linear Algebra is a nice book on this topic.

My impression is that people normally use Lapack to solve linear systems in C++, if they don't implement their own method. I could be wrong.

-
Thank you pro your answer. I'll try to summarize the properties of the matrix: It contains only natural numbers, they have no errorbars. I's probably sparse. There are multiple triangle-patterns inside the matrix. (Like smalle upper-triangle matrices, contained in the matrix). It may be overdetermined for some as well as underdetermined for other variables. The vector for the inhomegenity has real entries with errorbars. – Konstantin Schubert Aug 31 '11 at 11:47

Check out Numerical Recipes 3rd Edition: The Art of Scientific Computing, William H. Press, et al. It covers linear algebra in C++.

-
The book seeems to be available in my lib, so I will check it out and tell you what I found. Thank you! – Konstantin Schubert Aug 31 '11 at 11:35

Regarding implementation, I would recommend the open source software sage. In my experience its linear algebra is quite efficient (it uses C/C++ libraries) Here is an example

sage:mspace=MatrixSpace(QQ,3,3)
sage:ma=mspace.random_element();ma.right_kernel()
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[0 1 0]
sage: ma
[-1  0  0]
[-2  0 -2]
[-2  0  2]

-