If I define the following two matrices
A=rand(5000); (non-hermitian)
B=A+A'; (hermitian)
and find the time required to find inverse of them
tic;inv(A);toc;
tic;inv(B);toc;
I see that, surprisingly, it takes longer time to find inverse of the hermitian matrix comparing to the non-hermitian one! Additionally for the hermitian matrix it uses only single core in my quad-core computer! I checked this on other computers and also other versions of Matlab (up to 2009) and I got the same thing.
To fix the problem I simply added a small imaginary term to the hermitian matrix (e.g. 1i*1.e-100) to make it non-hermitian(!) which seem to be ridiculous. Can you guys please tell me if I'm doing something wrong here? Otherwise, apparently the "efficient algorithm" that is used to find inverse of hermitian matrix in Matlab is not really "efficient algorithm"!

On Dec 21, 1:17=A0am, "Farzad Mahfouzi" <farzad.mahfo...@gmail.com>
wrote:
> If I define the following two matrices
> A=3Drand(5000); (non-hermitian)
> B=3DA+A'; (hermitian)
> and find the time required to find inverse of them
> tic;inv(A);toc;
> tic;inv(B);toc;
> I see that, surprisingly, it takes longer time to find inverse of the her=
mitian matrix comparing to the non-hermitian one! Additionally for the herm=
itian matrix it uses only single core in my quad-core computer! I checked t=
his on other computers and also other versions of Matlab (up to 2009) and I=
 got the same thing.
> To fix the problem I simply added a small imaginary term to the hermitian=
 matrix (e.g. 1i*1.e-100) to make it non-hermitian(!) which seem to be ridi=
culous. Can you guys please tell me if I'm doing something wrong here? Othe=
rwise, apparently the "efficient algorithm" that is used to find inverse of=
 hermitian matrix in Matlab is not really "efficient algorithm"!

First of all, don't use TIC/TOC to time these things.
Use the profiler.

Second, don't time a single call of the function,
compute the average of a large number of calls.

Third, there is a difference between an *algorithm*
and an *implementation*. A good implementation of a
poor algorithm might well beat a poor implementation
of a good algorithm.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message <fd4f4996-52c8-454b-886a-502af107d340@j25g2000yqa.googlegroups.com>...
> On Dec 21, 1:17 am, "Farzad Mahfouzi" <farzad.mahfo...@gmail.com>
> wrote:
> > If I define the following two matrices
> > A=rand(5000); (non-hermitian)
> > B=A+A'; (hermitian)
> > and find the time required to find inverse of them
> > tic;inv(A);toc;
> > tic;inv(B);toc;
> > I see that, surprisingly, it takes longer time to find inverse of the hermitian matrix comparing to the non-hermitian one! Additionally for the hermitian matrix it uses only single core in my quad-core computer! I checked this on other computers and also other versions of Matlab (up to 2009) and I got the same thing.
> > To fix the problem I simply added a small imaginary term to the hermitian matrix (e.g. 1i*1.e-100) to make it non-hermitian(!) which seem to be ridiculous. Can you guys please tell me if I'm doing something wrong here? Otherwise, apparently the "efficient algorithm" that is used to find inverse of hermitian matrix in Matlab is not really "efficient algorithm"!
> 
> First of all, don't use TIC/TOC to time these things.
> Use the profiler.
> 
> Second, don't time a single call of the function,
> compute the average of a large number of calls.
> 
> Third, there is a difference between an *algorithm*
> and an *implementation*. A good implementation of a
> poor algorithm might well beat a poor implementation
> of a good algorithm.
> 
> Rune

Thanks for replying,
It seems that you haven't checked this simple test or your computer is single core.  Otherwise there should be something wrong with all the Matlabs around here!

Here's a result from my quadcore desktop computer:

>> tic;inv(A);toc;
Elapsed time is 13.996205 seconds.
>> tic;inv(B);toc;
Elapsed time is 39.508501 seconds.

The difference is always around 3-4 times which is because in the hermitian case my Matlab is using only one core. If I use only one core the difference is slightly different which is not my concern. 

As regards the "implementation" and profiler, please pay attention that this is just ONE line command!!

"Farzad Mahfouzi" <farzad.mahfouzi@gmail.com> wrote in message <iep47u$qj8$1@fred.mathworks.com>...

> 
> The difference is always around 3-4 times which is because in the hermitian case my Matlab is using only one core. If I use only one core the difference is slightly different which is not my concern. 

Odd indeed. If this is the case, then I guess the hermitian matrix solver is not yet been reworked to multi-thread.

Using tic-toc as you did is fine.

Bruno

"Farzad Mahfouzi" <farzad.mahfouzi@gmail.com> wrote in message <ieorm4$jrq$1@fred.mathworks.com>...
>
> To fix the problem I simply added a small imaginary term to the hermitian matrix (e.g. 1i*1.e-100) to make it non-hermitian(!) which seem to be ridiculous. Can you guys please tell me if I'm doing something wrong here? Otherwise, apparently the "efficient algorithm" that is used to find inverse of hermitian matrix in Matlab is not really "efficient algorithm"!
==============

I'm not aware of any efficient algorithm that applies to general non-Toeplitz, non-positive definite Hermitian matrices. I also wouldn't expect any efficient algorithms to kick in unless you invert using backslash. The following results (on my dual core laptop) seem to support this. I see significant acceleration with backslash for positive definite B and approximately equal speeds for general Hermitian B.

 N=3000; 
A=rand(N);  
X=rand(N); 

%%positive definite B case
B=A*A';

tic; A\X; toc; 
 Elapsed time is 4.958302 seconds.

tic; B\X;toc;
Elapsed time is 4.106105 seconds.

%%General Hermitian case
 B=A+A'; 

tic; A\X; toc; 
Elapsed time is 5.022854 seconds.

 tic; B\X;toc;
Elapsed time is 5.133918 seconds.

"Matt J" wrote in message <iepr7p$bis$1@fred.mathworks.com>...
> "Farzad Mahfouzi" <farzad.mahfouzi@gmail.com> wrote in message <ieorm4$jrq$1@fred.mathworks.com>...
> >
> > To fix the problem I simply added a small imaginary term to the hermitian matrix (e.g. 1i*1.e-100) to make it non-hermitian(!) which seem to be ridiculous. Can you guys please tell me if I'm doing something wrong here? Otherwise, apparently the "efficient algorithm" that is used to find inverse of hermitian matrix in Matlab is not really "efficient algorithm"!
> ==============
> 
> I'm not aware of any efficient algorithm that applies to general non-Toeplitz, non-positive definite Hermitian matrices. 

LDL decomposition? Admittedly I'm not sure it's any faster than LU. 

>I also wouldn't expect any efficient algorithms to kick in unless you invert using backslash. The following results (on my dual core laptop) seem to support this. I see significant acceleration with backslash for positive definite B and approximately equal speeds for general Hermitian B.
> 

This again begs for a question: why on earth Matlab does not use "\" internally in they inverse?

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ieqc34$f14$1@fred.mathworks.com>...
>
> 
> This again begs for a question: why on earth Matlab does not use "\" internally in they inverse?
==========

Well, for general matrices "\" seems to do be a slightly slower solution (even though we know, I guess, that it is more numerically accurate):


>> A=rand(3000); I=speye(3000);
>> tic; A\I; toc
Elapsed time is 5.128218 seconds.
>> tic; inv(A); toc
Elapsed time is 4.711147 seconds.

> I'm not aware of any efficient algorithm that applies to general non-Toeplitz, non-positive definite Hermitian matrices. I also wouldn't expect any efficient algorithms to kick in unless you invert using backslash. The following results (on my dual core laptop) seem to support this. I see significant acceleration with backslash for positive definite B and approximately equal speeds for general Hermitian B.

At the time of writing the question, based on 2-3 experiments on single core machine (actually I  used only one core in my quadcore), I thought inv of non-hermitian is slightly faster. But apparently it's not the case. I don't care about ~10 percent faster or slower, anyhow. As mentioned by Bruno the problem is that, apparently for hermitian matrices their algorithm is not written for multi-thread calculation. I don't understand why should they introduce another algorithm for hermitian matrices while its speedup is hardly noticeable and it's not written in multi-thread form. It's like a joke that I have to add 1i*1.e-100 to the hermitian matrix to make it non-hermitian and have multi-thread calculation. 
In my problems the matrices are not positive definite and not only I don't see any speedup by using "\", it seems to be a bit slower than inv in both hermitian and non-hermitian cases (as mentioned earlier).
As regards the efficient algorithm, it's actually not hard to imagine a simple modification to LU decomposition and use symmetric property (I'm not sure about complex matrices) of the matrix to find inverse and have ~2X speedup.
Farzad.

"Farzad Mahfouzi" wrote in message <ieqsaa$fkh$1@fred.mathworks.com>...
> In my problems the matrices are not positive definite and not only I don't see any speedup by using "\", it seems to be a bit slower than inv in both hermitian and non-hermitian cases (as mentioned earlier).

FWIW, here is my timings:

>> A=randn(5000); %(non-hermitian);
>> B=(A+A'); %(hermitian)

>> tic;inv(A);toc;
Elapsed time is 17.869812 seconds.
>> tic;inv(B);toc;
Elapsed time is 32.179434 seconds.

>> I=speye(size(A));
>> tic;A\I;toc;
Elapsed time is 21.415077 seconds.
>> tic;B\I;toc;
Elapsed time is 20.572000 seconds.
>> 

2010B-64 bit, Win7, Intel i5 (4 cores I think).

Bruno

> >> A=randn(5000); %(non-hermitian);
> >> B=(A+A'); %(hermitian)
> 
> >> tic;inv(A);toc;
> Elapsed time is 17.869812 seconds.
> >> tic;inv(B);toc;
> Elapsed time is 32.179434 seconds.
> 
> >> I=speye(size(A));
> >> tic;A\I;toc;
> Elapsed time is 21.415077 seconds.
> >> tic;B\I;toc;
> Elapsed time is 20.572000 seconds.

Thanks you for the confirmation. I appreciate that!
I didn't mean that B\I doesn't use multi-thread calculation. I meant for one core case (using maxNumCompThreads(1)) the B\I takes longer time than inv(A).
BTW, is your cpu i5-450M? Because my laptop has the same cpu but the timing is more than yours (e.g. in the first case, yours is 17 seconds but mine is ~25)!

"Farzad Mahfouzi" wrote in message <ier6gf$blj$1@fred.mathworks.com>...

> BTW, is your cpu i5-450M?

Yes 2.4GHz

Bruno