## Why is inv(A) slow?

### Why is inv(A) slow?

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

--

Kindly
---------------------------------------------------
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?

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

> --

> Kindly
> ---------------------------------------------------
> 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?

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?

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

--