# 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.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!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?

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

**the distances. They have error bars. Thus, they are not exact. The algorithm**

*measure*shall find the solution that fits best.

*

**It may be that there is**

It may be that we measure the same route twice or even more often. The resutlts may be

*too much*information for a exact solutiondifferent, since they have errors. The algorithm should use the resulting additional

information.

*

**It may be that there is**

Maybe we know the length of ABEF", but there is no way to get any information for EF"

*not*enough information for a solution.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.

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 the algorithm gave some information about how likely a masured distance is wrong.

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.

Here is my Email-address:

[email protected]

Since this is a private project, we can't offer you any money for your help, but we'll mention you

if/when we publish our results.

Sincerely,

Konstantin Schubert (and Heiko Burau)

PS: I apologize for not having used LaTeX.