Selected solution of linear equations

[Gabor Ladanyi]

Hi All,

In my work I would like to solve a thousands of moderate size systems of linear equations, parallelly. The uniquum in my problem is that, I am not interested in the whole solutions of the systems, but only several elements of the solution vectors are interesting.

To be more strict:
Let a set of system of linear equations be given:
A⁽ⁱ⁾⋅x⁽ⁱ⁾=y⁽ⁱ⁾, i=1..N,
All the matrices A⁽ⁱ⁾ and vectors y⁽ⁱ⁾ are real.
The dimensions of the systems are equal and it is typical between 10 and 39.
The number of systems is typical N>5000.
The problem for example is to determine the x⁽ⁱ⁾₁, x⁽ⁱ⁾₃,
x⁽ⁱ⁾₄ for all i=1..N.

The question: Have you ever heard any similar selective solver for linear equations? Direct and itterative solvers are also interesting for me.
Thank you for your help in advance!

G. Ladanyi

 

[NFuller]

LU factorization would probably suffice for what you are doing. If you are only looking for certain elements of the solution vector, then put those rows at the bottom of the matrix. When you back substitute, you will only need to do it for these bottom rows, which will save some computation time.

 

[scottdave]

I was going to suggest Cramer's Method. I don't know if this is more or less calculations than LU factorization, though. (an important consideration with the number of different systems that you want to solve).

I don't remember exactly how LU works. I'd have to do some reading on it. I think with LU you do need to take the determinant of the matrix. I'm not sure what else.
With Cramer's Method, you would take 1 determinant plus a determinant for each element that you want to solve for, then divide. One concern that I could see is potential rounding, depending on how big the products that you generate, are.

 

[NFuller]

I don't remember exactly how LU works. I'd have to do some reading on it. I think with LU you do need to take the determinant of the matrix. I'm not sure what else.
With Cramer's Method, you would take 1 determinant plus a determinant for each element that you want to solve for, then divide. One concern that I could see is potential rounding, depending on how big the products that you generate, are.

Determinants are very computationally expensive and are almost never used to solve big matrices. LU factorization does not require one to find a determinant, it is basically a clever form of Gaussian elimination.

One question for the OP, are the matrices that you are using nonsingular?

 

[scottdave]

Determinants are very computationally expensive and are almost never used to solve big matrices. LU factorization does not require one to find a determinant, it is basically a clever form of Gaussian elimination.

Good to know. Like I said, it has been awhile, and I couldn't recall exactly how LU is used or calculated.

 

[Gabor Ladanyi]

My matrices are non singular.

Gaussian elemination (GE) with selected back substituting seems to be good enough for the first glimps. I could substitute back only the interesting rows. It means, I choose the order of the soultion to generate the interesting elements first. When they are calculated I do not continue the calculation. (Order1)

Unfortunately, sometimes the matrices are badly conditioned and pivoting version of GE could be more accurate. If I know well, pivoting needs the changing of rows. It is almost "equal" with the selection of order of the solution. (Order2)

I am afraid, (Order1) and (Order2) are not the same, I have to choose between accuracy or speed.

I hope my ideas were clear... What do you think?

 

[NFuller]

Pivoting is relatively cheap and will not cost you much speed, you should almost always do it.

 

[scottdave]

Reading some of these posts and doing some searching of the terms, some of it is coming back, but I realize I have forgotten quite a bit.

 

[scottdave]

To brush up, I'm considering this edX course: Linear Algebra - Foundations to Frontiers - LAFF for short. I've taken a couple of edX courses, and enjoyed them.