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

Questions
,
1

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`*)
2

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`*)
3

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.

4

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.

5

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

Many elaborated packages have to be downloaded at first use.

6

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
7

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.