Path: news.mathworks.com!not-for-mail
From: "Tim Davis" <davis@cise.ufl.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: calculating the inverse efficiently (not for solving equations :-) )
Date: Wed, 2 Apr 2008 00:43:01 +0000 (UTC)
Organization: University of Florida
Lines: 83
Message-ID: <fsukql$df3$1@fred.mathworks.com>
References: <fsu1r6$ib3$1@fred.mathworks.com>
Reply-To: "Tim Davis" <davis@cise.ufl.edu>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1207096981 13795 172.30.248.37 (2 Apr 2008 00:43:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 2 Apr 2008 00:43:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 45902
Xref: news.mathworks.com comp.soft-sys.matlab:460434



"M E" <gitsnedbutzi@hotmail.com> wrote in message
<fsu1r6$ib3$1@fred.mathworks.com>...
> Hi,
> 
> well most of you probably think "Oh no, not another one
> trying to solve a system of linear equations using the
> matrix inverse", but luckily for those guys I don't need it
> for that :-)
> 
> So my problem is that after some calculations I got stuck
> with an equation of the following kind:
> 
> (A*B^-1*C)*x=y
> 
> As the matrix B is multiplied with A and C there's no way
> (or at least I don't know of any) to get around the problem
> of knowing the full inverse of B.
> 
> Some important properties for B are, that it's symmetric and
> sparse. Yes, I know having the inverse will destroy the
> sparisty :-)
> 
> 
> So far the possibilities for calculating the inverse of B, I
> have come up with are:
> *LU decomposition: tends to fail because B is rather large
> and therefore my computer runs out of memory
> *Cholesky decomposition: not much more efficient than the LU
> decomposition (n^3/3 compared to 2n^3/3)
> 
> I also thought of using eigenvalues, but that wouldn't help
> much since you need the inverse of the matrix with the
> eigenvectors.
> 
> I hope that I could give anyone enough insight into my
> problem...
> 
> Does anyone know another efficient way for calculating the
> inverse for sparse symmetric matrices, or maybe to simplify
> or transform the upper equation to make it less costly?
> 
> Thanks in advance!!
> 
> Albert Buehrli
> 
> 

If you ever find yourself multiplying by the inverse, then
you know one thing for certain.  You know, for sure, that
you don't know what you're doing.  One needs never, ever,
ever multiply by the inverse.  Multiplying by the inverse is
mathematically equivalent to solving a system of linear
equations, but it is an awful computational replacement for
the latter.

You really *are* solving a system of equations, either B*z=C
for z, or you are solving A=w*B for w.  Both are systems of
linear equations.

Instead of inv(B)*C, you should use B\C instead.  Or,
replace A*inv(B) by A/B.

You gave as the equation:

(A*B^-1*C)*x=y

does this mean you know A, B, C, and x, and you want to
compute y?  Or are you solving for x?  If it's the latter,
then what you are should do is this:

x = ((A/B)*C)\y

or

x = (A*(B\C))\y

If you have x and want to compute y, then do

y = ((A/B)*C)*x

or

y = (A*(B\C))*x