This is not the document you are looking for? Use the search form below to find more!

Report

# LinAlgProblem

Document Description
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!
File Details
• File size: 133.79kb
• Pages: 3
• Tags: math, linear algebra, numerics, problem
• content preview
Submitter
• Name: Konstantin
Embed Code:

#### Showing 1 comment

by Konstantin on August 28th, 2011 at 05:20 pm
Content 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.
k.schubert@mailbox.tu-dresden.de
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.

LinAlgProblem

Share LinAlgProblem to:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share LinAlgProblem as:

From:

To:

Share LinAlgProblem.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

Share LinAlgProblem as:

Copy html code above and paste to your web page.