Message Boards Message Boards

2
|
2047 Views
|
6 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Inverse[] Slows 1000x by selecting Method in larger systems

I was looking for speed with Inverse[] by trying different methods when I came across this.

Inverse[] with its default Method->Automatic is extremely fast. The documentation of Inverse[] says that it will choose one of three methods if left to Automatic, but if you choose any of the three they are all orders of magnitude slower- I mean 1000x or more slower on a large system (n=500). Is there another method being chosen? Maybe it's attempting symbolic computation or no accelerator (i.e., MKL LAPACK) is used?

Mathematica documentation does tend to be a bit cryptic for my taste. It would be interesting to know more about what is going on under the hood here. References and/or documentation on the algorithms would be of great use.

Why the slow timings while Inverse[] left alone is so fast? Thanks in advance.

V13.2 On Core I9-10900K CPU@3.70GHz Windows 11 PC; 

A = RandomReal[10, {500, 500}];
RepeatedTiming[Inverse[A, Method -> Automatic], 10][[1]] (*sec=0.0033 !!!*)
RepeatedTiming[Inverse[A, Method -> "CofactorExpansion"], 10][[1]] (*sec=3.3930731`*)
RepeatedTiming[Inverse[A, Method -> "DivisionFreeRowReduction"], 10][[1]](*sec=10.6844523`*)
RepeatedTiming[Inverse[A, Method -> "OneStepRowReduction"], 10][[1]](*sec=10.9590677`*)
POSTED BY: Neal Maroney
6 Replies
Sort By:

The exercise, as it turned out, was point out that the documentation should reflect the default for reals is MKL-BLAS/LAPACK and not one of the three methods for exact/symbolic .

Don't know what is accomplished by the eigenvalues and complex numbers; like to know. Inverse is as old as mathematica (1988) and RepeatedTiming is a built-in symbol from 2015. Remember when getting the timing the first part is the time in seconds and the second part is the output . Suppressing output means only printing the first part [[1]].

If your concerned about scale/accuracy then the timing differences will persist in lower order systems because of the Intel-MKL use. It is designed so as to vectorize and parallelize taking full advantage of the CPUs architecture which makes it the industry standard-- and that is Intel.
POSTED BY: Neal Maroney

Since the whole procedure seemed a bit strange, I changed the Matrix to normal real values and and changed it for each run and suppress any form of output. 

In[1]:= A = RandomReal[{-1.0, 1.0}, {500, 500}]/7.75;    
In[2]:=  eg = Eigenvalues[A];    
In[3]:= Det[A]    
Out[3]= 1393.37    
In[4]:= Times @@ eg    
Out[4]= 1393.37 - 8.07086*10^-13 I    
In[5]:= Mean[Abs[eg]]    
Out[5]= 1.11294

p := 0.77 + 0.11 I;
RepeatedTiming[ Inverse[A + p++, Method -> Automatic];, 10](*sec=0.0033!!!*)

p := 0.77 + 0.11 I;    {0.0212489, Null}
    Quiet[RepeatedTiming[Inverse[A + p++, Method -> "CofactorExpansion"];,   10](*sec=3.3930731`*)]

{49.676, Null}

etc.

I suppose that the fast execution happend with overflow suppressed. The original RandomMatrix has Det something like

Det[RandomReal[10, {500, 500}]] 

1.095242615329556*10^798
POSTED BY: Roland Franzius

Did you allow access to the internet in the Menu/Help?

Many elaborated packages have to be downloaded at first use.
POSTED BY: Roland Franzius

Thanks for clarification Daniel that makes sense.

Tried to repeat the behavior Roland demonstrated but could not- I got the same timings. Don't know what is going on there, but interested to know.
POSTED BY: Neal Maroney

You are correct that those methods apply for exact or symbolic inputs. For matrices if reals, default use of Lapack with MKL or other BLAS library will be much faster.
POSTED BY: Daniel Lichtblau

There is something wrong

on a i5 10xxx notebook 

A = RandomReal[10, {500, 500}];

RepeatedTiming[Inverse[A, Method -> Automatic];, 10]

{0.0081165892578125`, Null}
MaxMemoryUsed[]
56525776

(*sec=0.0033!!!*)

RepeatedTiming[Inverse[A, Method -> "CofactorExpansion"];, 10] 

{5.866210222244263`*^-7, Null}

MaxMemoryUsed[]
45928008

(*sec=3.3930731`*)

RepeatedTiming[Inverse[A, Method -> "DivisionFreeRowReduction"];, 10]

{5.844862222671509`*^-7, Null}
MaxMemoryUsed[]
45927856
(*sec=10.6844523`*)

RepeatedTiming[Inverse[A, Method -> "OneStepRowReduction"];, 10]
{6.003846764564514`*^-7, Null}
MaxMemoryUsed[]
45928008
(*sec=10.9590677`*)
POSTED BY: Roland Franzius
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract