Re: Newbie question: big matrix calculations
- To: mathgroup at smc.vnet.net
- Subject: [mg9281] Re: [mg9253] Newbie question: big matrix calculations
- From: Daniel Lichtblau <danl>
- Date: Mon, 27 Oct 1997 02:46:52 -0500
- Sender: owner-wri-mathgroup at wolfram.com
Dennis Wayne Scott wrote:
> <...>
> I have three 100x100 sparse (diagonal) matrices (matrxD, matrxU, and
> matrxL) and three 100x1 matrices (b, x2, and x1), and I'm performing
> several operation on them:
>
> x2 = -Inverse[matrxD].(matrxL+matrxU).x1+Inverse[matrxD].b;
>
> I have to do it MANY, MANY times... with a 5x5 matrix it takes a few
> minutes, but with a 100x100 it takes longer than eight hours (and still
> running). Does anyone (offhandedly) know of a way to reduce the time
> this takes for Mathematica to solve?
>
> <...>
>
> --
> Dennis W. Scott, Jr.
> University of Illinois at Urbana dscott at ews.uiuc.edu
> ----------------------------------------------------------------
> Aspiring Electrical Engineer "I want to know God's
> thoughts...
The operation matrix . matrix for n x n matrices is O(n^3) in
complexity. Since your matrices are diagonal and do not change, it
would be much faster (O(n)) to represent them as vectors and use
vector.vector operations. The inverse will just be the vector of
reciprocals.
Say the vector of reciprocals for your your main-diagonal matrix is
{a[1],...,a[n]} (all non-zero), the vector for your sub-diagonal matrix
is {b[1],...,b[n-1]}, that for your super-diagonal is
{c[1],...,c[n-1]}, and the vector x is {x[1],...,x[n]}. Then simple
manipulation shows that (using your notation again)
Inverse[matrxD].(matrxL+matrxU).x1
is given by
{a[1]*c[1]*x[2], a[2]*b[1]*x[1] + a[2]*c[2]*x[3], ... ,
a[n-1]*b[n-2]*x[n-2] + a[n-1]*c[n-1]*x[n], a[n]*b[n-1]*x[n-1]}
Well, maybe you should double-check this, I might have messed up some
subscripts.
Once you get it working, it will be alot faster than what you have.
Daniel Lichtblau
Wolfram Research
danl at wolfram.com