Re: Giant linear system of equations

Alfred (Alfred@xxxxxxxxxx) wrote:
with editing...
: What's best algorithm to solve a giant general linear system of equations?

: I have 10^6 equations, so a 10^6*10^6 matrix of coefficients, no symmetries
: ---> N^2 coefficients. I know that matrix is invertible, so the solution is
: unique.

: Clearly I cannot store that matrix on memory or on HD.

: I must generate a coefficient of matrix at every call.

: Any suggestion?

Sounds like a large photogrammetric mapping project,
with highly-sparse matrices.
I've done a least-squares adjustment on more than
one of these.
I used APL2 and blocking. The blocking algorithm
was obtained from a book on matrices by Fadeev
and Fadeeva, but the title of the book eludes me.
I remember having to use some sort of intelligent
blocking algorithm programmed in APL, but it was
so long ago that the whole process is now gone from
my head and my notes. I remember it running overnight
on an old IBM 286-AT, with post-analysis. The process
used the inversion routine that comes standard with
any APL interpreter, but the inversions were done on
the blocks not the full matrix. The majority of the
blocks were null-matrices, so they could be ignored
in the inversion process.

Seems to me that the process would take no more than
a few minutes on a P4 with a current APL2 interpreter.
Maybe that's not fast enough today.

Regards. RAF
.

Relevant Pages

  • Re: fast matrix multiplication
    ... but what about the inversion? ... > coefficient over inversion than you are ever going to see with polishing. ...
    (comp.lang.fortran)
  • THEOREM: I <= 4M in GF(p^n)
    ... That is field inversion is no more costly than the cost of 4 field ... pass algorithm that in the end computes the inverses in leafs). ... int NX= high_digit, ... Inversion" because of the number of extension field multiplications ...
    (comp.theory)
  • inversion of prime field elements on smartcards (or other 8bit MCUs)
    ... the literature proposes to use the extended euclidean algorithm ... The first algorithm uses helper variables for which no upper bounds ... where can I find an algorithm for inversion in prime ...
    (sci.crypt)