Why is inv(A) slow?

Why is inv(A) slow?

Post by Konrad Den End » Sat, 08 Nov 2003 04:05:49



Regard this code:
n = 700;A = randn(n);b = randn(n, 1);tic; x = inv(A) * b; toc  % (1)
tic; y = A \ b; toc   % (2)
The time for inv-method (1) is slower longer than \-method (2).
I understand (2) will use Gauss-elimination but what i can't
really put my finger on is why the big difference in time occurs.
(1) needs to go through ALL the elements but on the other hand,
so does (2).

Does (2) only work on a part of the matrix (perhaps the lower
triangle?) and hence the time difference? Still, it should be
about 1:2 not more.

--

Kindly
Konrad
---------------------------------------------------
May all spammers die an agonizing death; have no burial places;
their souls be chased by demons in Gehenna from one room to
another for all eternity and more.

Sleep - thing used by ineffective people
            as a substitute for coffee

Ambition - a poor excuse for not having
                 enough sence to be lazy
---------------------------------------------------

 
 
 

Why is inv(A) slow?

Post by A. [Sena] Sopaheluwaka » Sat, 08 Nov 2003 07:29:37


Hi ...
calculating the inverse of a matrix is generally considered to have O(n^2)
operations.
While by solving the system y = A\b, matlab decomposes the matrix [simply
stated,] into lower and
upper triangular matrix first, and then a straight forward algorithm to
solve this is much
"cheaper" [in the calculation order sense], rough approximation is O(n+n) =
O(2n).
Thats why solving the system is much faster ...

Regards,
Sena



Quote:> Regard this code:
> n = 700;A = randn(n);b = randn(n, 1);tic; x = inv(A) * b; toc  % (1)
> tic; y = A \ b; toc   % (2)
> The time for inv-method (1) is slower longer than \-method (2).
> I understand (2) will use Gauss-elimination but what i can't
> really put my finger on is why the big difference in time occurs.
> (1) needs to go through ALL the elements but on the other hand,
> so does (2).

> Does (2) only work on a part of the matrix (perhaps the lower
> triangle?) and hence the time difference? Still, it should be
> about 1:2 not more.

> --

> Kindly
> Konrad
> ---------------------------------------------------
> May all spammers die an agonizing death; have no burial places;
> their souls be chased by demons in Gehenna from one room to
> another for all eternity and more.

> Sleep - thing used by ineffective people
>             as a substitute for coffee

> Ambition - a poor excuse for not having
>                  enough sence to be lazy
> ---------------------------------------------------


 
 
 

Why is inv(A) slow?

Post by Matt Wolinsk » Sat, 08 Nov 2003 10:47:02


To calculate B=inv(A), you have to solve

A*B=I=eye(n)

This is the same thing as

for i=1:n
     B(:,i)=A / I(:,i);
end

i.e. you need to solve n linear systems: one for each column of I

So inv(A) will take O(n*T) time, where
T = time to solve A / b

HTH,

Matt

 
 
 

Why is inv(A) slow?

Post by John D'Erric » Sat, 08 Nov 2003 10:58:47




Quote:> Hi ...
> calculating the inverse of a matrix is generally considered to have O(n^2)
> operations.
> While by solving the system y = A\b, matlab decomposes the matrix [simply
> stated,] into lower and
> upper triangular matrix first, and then a straight forward algorithm to
> solve this is much
> "cheaper" [in the calculation order sense], rough approximation is O(n+n) =
> O(2n).
> Thats why solving the system is much faster ...

Yes, there is a difference in the two methods, but
you have the orders wrong.

Inverting a matrix is an O(n^3) operation. The
solution via factorization takes about 1/3 of that.
Both grow with the cube of the matrix order.

As an example, try this (only if you happen to have
an old enough copy of matlab* around. Flops
was a nice tool sometimes.

n = 40;
A=rand(n,n);b=rand(n,1);
flops(0),x=inv(A)*b;f0=flops;flops(0),x=A\b;flops/f0
ans =

         0.393535249239947

n=100;
A=rand(n,n);b=rand(n,1);
flops(0),x=inv(A)*b;f0=flops;flops(0),x=A\b;flops/f0
ans =

         0.358123223719749

n=500;
A=rand(n,n);b=rand(n,1);
flops(0),x=inv(A)*b;f0=flops;flops(0),x=A\b;flops/f0
ans =

         0.33838662621814

It looks like a factor of 3 to me.

HTH,
John D'Errico

--
There are no questions "?" about my real address.

The best material model of a cat is another, or
preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945