# LinAlgProblem

### Text-only Preview

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!

Here it is:
We have a graph. It has nodes and it has connections between the nodes. But not all of the nodes
are connected. Connections are mainly between neighboured nodes.
We measure the distances along some routes.
For example:
Say: The way: ABEFGIN" is 10 units long.

We now measure the distances along many more routes.
(The way ABCN" is 8.6 units long. The way ABE" is 3.5 units long. Etc....)
From all this data, we now want to calculate the atomic distances: How far is from A to B? from B
to E? From J to C?

As far as we can see, this leads to a simple system of linear eqations that have to be solved.
...
AB"+"BE"=3.5
AB"+"BC"+"CN"=8.6
etc....
=> AB"=? BE"=? etc...
Let's specify the properties of our problem:
*
Coefficients of the variables are natural numbers.
It may happen, that we have the way AB" passed twice in route, thus leading to an
equation like: 2* "AB"+ .....+...+....= 5.6
But it will never occur that we pass AB" 1.5 times.
*
It may be possible that the system cannot be solved exactly.
We measure the distances. They have error bars. Thus, they are not exact. The algorithm
shall find the solution that fits best.
*
It may be that there is too much information for a exact solution
It may be that we measure the same route twice or even more often. The resutlts may be
different, since they have errors. The algorithm should use the resulting additional
information.
*
It may be that there is not enough information for a solution.
Maybe we know the length of ABEF", but there is no way to get any information for EF"
out of our data.
It would be great if the algorithm could handle this case. It souldn't return a random number
for EF", but a return value that shows that there is actually no way to get a result for EF".
*
It would be good if the algorithms took into account the errorbars of the measured
distances.

*
There is a special pattern that will occur freqently.

Most of the time (but not always), the masured path is consecutive and only a node longer
than the previous one. To illustrate this:
In the matrix of the coefficients, that leads to triangle-patterns.
*
-This would be good:
If the algorithm gave some information about how likely a masured distance is wrong.
If some result doesn't fit at all with the (redundant) others, the algorithm should indicate this.
If you know an algorithm that you think we may be interested in, let us know! If you know an
implementation (a c++ library), let us know!
If you have any further questions, please ask us. I'm also available for an online chat in IRC.