Is Matrix inversion O(N^3)?

Hi,

I do not know much about O notation, except that it gives a
theoretical indication of the performance of some algorithms.

I have seen a reference somewhere (have to look it up, but think it
was in "Numerical recipes in C") that matrix inversion is O(N^3).

Is this true for all sizes of N, assuming an (N x N) matrix, or does
the inversion of large matrices of size (N x N) approach O(N^3)? 
I.e., for matrices with small N, the actual performance would be
better than O(N^3)?

Would it then be better to try and break large (N x N) matrices into
smaller matrices and invert these, if it is possible?

Your time, effort and suggestions will be greatly appreciated?
Jaco Versfeld

On 12 May 2004 07:12:11 -0700, Jaco Versfeld wrote:
> Hi,

> I do not know much about O notation, except that it gives a
> theoretical indication of the performance of some algorithms.

> I have seen a reference somewhere (have to look it up, but think it
> was in "Numerical recipes in C") that matrix inversion is O(N^3).

The usual algorithms are O(N^3), but there is a class of algorithms such
as Strassen's algorithm that improves on that.  I think it's something
like O(N^2.83) for Strassen and somewhat better for some other algorithms
based on a similar technique.  The basic idea is to reduce the number of
multiplications required, at the cost of many extra additions.  This can be an
advantage when you realize that the algorithm can be applied recursively to
block submatrices, where matrix multiplication is much slower than matrix
addition.

> Is this true for all sizes of N, assuming an (N x N) matrix, or does
> the inversion of large matrices of size (N x N) approach O(N^3)? 
> I.e., for matrices with small N, the actual performance would be
> better than O(N^3)?

The O notation actually doesn't tell you anything at all about
performance for small N.  It's only relevant to the asymptotic behavior
as N -> oo.

And it doesn't automatically follow that an O(N^2.83) algorithm is better
(faster, easier) than one that is O(N^3), since the O natation only tells
you about the time up to some multiplicative constant, which in practice
is much larger for the Strassen-class algorithms than for standard
Gaussian elimination.  This means that the potential advantage of using
Strassen only exists for very large matrices.

> Would it then be better to try and break large (N x N) matrices into
> smaller matrices and invert these, if it is possible?

Not exactly, but recursion is part of the algorithm.

> Your time, effort and suggestions will be greatly appreciated?
> Jaco Versfeld


-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>

"Jaco Versfeld" <jaco_versfeld@hotmail.com> wrote in message news:e48813da.0405120612.22b81029@posting.google.com...
> Is this true for all sizes of N, assuming an (N x N) matrix, or does
> the inversion of large matrices of size (N x N) approach O(N^3)?
> I.e., for matrices with small N, the actual performance would be
> better than O(N^3)?

       Big O doesn't care what happens to the small N either way.
While the classical Gaussian elimination algorithm is O(N^3), there
are faster algorithms.  The current record is O(N^2.376).  However,
the faster algorithms are more challenging to implement as computer
programs and sacrifice numerical stability.  See

     <http://mathworld.wolfram.com/StrassenFormulas.html>

for some related info.

On 12 May 2004 07:12:11 -0700, Jaco Versfeld <jaco_versfeld@hotmail.com> wrote:
> Hi,
>
> I do not know much about O notation, except that it gives a
> theoretical indication of the performance of some algorithms.

DAGS on "Big O Notation"  Tons of references.  I like "Discrete
Mathematics and its Application(s)" for a good, rigorous, discussion of
all things Discrete.

>
> I have seen a reference somewhere (have to look it up, but think it
> was in "Numerical recipes in C") that matrix inversion is O(N^3).
>
> Is this true for all sizes of N, assuming an (N x N) matrix, or does
> the inversion of large matrices of size (N x N) approach O(N^3)? 
> I.e., for matrices with small N, the actual performance would be
> better than O(N^3)?

Nope.  Big O notation (now that you've looked it up) is for all N.

> Would it then be better to try and break large (N x N) matrices into
> smaller matrices and invert these, if it is possible?

With matrices there are a ton of special cases that make your life
easier:  Say for example you know your matrix is invertable beforehand,
the matrix is sparse with certain properties . . . the matrix is already
in row-reduced form.  For certain classes of problems, all of these
simplifications apply.

"Numerical Recipies in ..." primary value is in telling you where to go
for better information.  Their implementations are better in
FORTRAN--the're all based on Fortran IV.  All other languages are
translations of varying success.  I found their simple functions more
useful than their vector-matrix operations:  Their matrix and vector
libraries rely on "Undefined Behavior" which is NEVER good.  Their fft
code works. 

"Jaco Versfeld" <jaco_versfeld@hotmail.com> wrote in message
news:e48813da.0405120612.22b81029@posting.google.com...
> Hi,
>
> I do not know much about O notation, except that it gives a
> theoretical indication of the performance of some algorithms.
>
> I have seen a reference somewhere (have to look it up, but think it
> was in "Numerical recipes in C") that matrix inversion is O(N^3).
>
> Is this true for all sizes of N, assuming an (N x N) matrix, or does
> the inversion of large matrices of size (N x N) approach O(N^3)?
> I.e., for matrices with small N, the actual performance would be
> better than O(N^3)?
>
> Would it then be better to try and break large (N x N) matrices into
> smaller matrices and invert these, if it is possible?
>
> Your time, effort and suggestions will be greatly appreciated?
> Jaco Versfeld

Hello Jaco,
Yes the general effort for matrix inversion is O(N^3) but in Numerical
Recipes (in C) they do give some details for an algo that is O(N^2.7).
However the overhead of keeping track of what is going on seems to diminish
the advantage - and for small matrices the added complication is not worth
it. There are some iterative methods for solving systems of equations. Do
you have a particular system you wish to solve or do you just want to invert
a matrix?

The way I would handle the problem would be to write a c++ object for your
GF arithmetic and overload the standard arithmatic operators to work in your
GF. Then just use a standard matrix inversion routine. I did this with a
different class of numbers and it worked like a champ.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz

Hi Jaco,

In a problem on p.287, [1] states that matrix inversion
requires n^3 multiplications/divisions and n^3 - 2*n^2 + n
additions/subtractions. There is also some discussion on
the problem in [2] but (surpisingly) not an explicit derivation
of the complexity.

Also, my coding theory professor stated this in a class just this
past (Spring) semester.

--Randy

[1] = @BOOK{burden,
  title = "{Numerical Analysis}",
  author = "Richard~L.Burden, J.~Douglas~Faires, Albert~C.~Reynolds",
  publisher = "Prindle, Weber and Schmidt",
  edition = "second",
  year = "1981"}

[2] = @BOOK{artofcomputerprogrammingb,
  title = "{The Art of Computer Programming, Volume 2: Seminumerical Algorithms",
  author = "Donald~E.~Knuth",
  publisher = "Addison-Wesley",
  edition = "third",
  year = "1998"}


jaco_versfeld@hotmail.com (Jaco Versfeld) writes:

> Hi,
> 
> I do not know much about O notation, except that it gives a
> theoretical indication of the performance of some algorithms.
> 
> I have seen a reference somewhere (have to look it up, but think it
> was in "Numerical recipes in C") that matrix inversion is O(N^3).
> 
> Is this true for all sizes of N, assuming an (N x N) matrix, or does
> the inversion of large matrices of size (N x N) approach O(N^3)? 
> I.e., for matrices with small N, the actual performance would be
> better than O(N^3)?
> 
> Would it then be better to try and break large (N x N) matrices into
> smaller matrices and invert these, if it is possible?
> 
> Your time, effort and suggestions will be greatly appreciated?
> Jaco Versfeld

-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

Dave Seaman wrote:

   ...

> The usual algorithms are O(N^3), but there is a class of algorithms such
> as Strassen's algorithm that improves on that.  I think it's something
> like O(N^2.83) for Strassen and somewhat better for some other algorithms
> based on a similar technique.  The basic idea is to reduce the number of
> multiplications required, at the cost of many extra additions.  ...

That's not a useful trade on hardware with single-cycle multipliers. For
DSPs, the O() calculations need to use the same cost for addition and
multiplication, and a relatively exorbitant cost for division.

   ...

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On Wed, 12 May 2004 13:05:17 -0400, Jerry Avins wrote:
> Dave Seaman wrote:

>    ...

>> The usual algorithms are O(N^3), but there is a class of algorithms such
>> as Strassen's algorithm that improves on that.  I think it's something
>> like O(N^2.83) for Strassen and somewhat better for some other algorithms
>> based on a similar technique.  The basic idea is to reduce the number of
>> multiplications required, at the cost of many extra additions.  ...

> That's not a useful trade on hardware with single-cycle multipliers. For
> DSPs, the O() calculations need to use the same cost for addition and
> multiplication, and a relatively exorbitant cost for division.

It may be a useful trade if you are comparing multiplication of, say,
1024x1024 matrices with addition of those matrices.  The cost is most
definitely not the same.


-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>

Dave Seaman wrote:

> On Wed, 12 May 2004 13:05:17 -0400, Jerry Avins wrote:
> 
>>Dave Seaman wrote:
> 
> 
>>   ...
> 
> 
>>>The usual algorithms are O(N^3), but there is a class of algorithms such
>>>as Strassen's algorithm that improves on that.  I think it's something
>>>like O(N^2.83) for Strassen and somewhat better for some other algorithms
>>>based on a similar technique.  The basic idea is to reduce the number of
>>>multiplications required, at the cost of many extra additions.  ...
> 
> 
>>That's not a useful trade on hardware with single-cycle multipliers. For
>>DSPs, the O() calculations need to use the same cost for addition and
>>multiplication, and a relatively exorbitant cost for division.
> 
> 
> It may be a useful trade if you are comparing multiplication of, say,
> 1024x1024 matrices with addition of those matrices.  The cost is most
> definitely not the same.

Indeed, but few programmable processors have instructions to deal with 
matrices. I assume that the primitives in the O() calculations deal with 
executable instructions.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

On Wed, 12 May 2004 13:58:01 -0400, Jerry Avins wrote:
> Dave Seaman wrote:

>> On Wed, 12 May 2004 13:05:17 -0400, Jerry Avins wrote:

>>>Dave Seaman wrote:


>>>   ...


>>>>The usual algorithms are O(N^3), but there is a class of algorithms such
>>>>as Strassen's algorithm that improves on that.  I think it's something
>>>>like O(N^2.83) for Strassen and somewhat better for some other algorithms
>>>>based on a similar technique.  The basic idea is to reduce the number of
>>>>multiplications required, at the cost of many extra additions.  ...


>>>That's not a useful trade on hardware with single-cycle multipliers. For
>>>DSPs, the O() calculations need to use the same cost for addition and
>>>multiplication, and a relatively exorbitant cost for division.


>> It may be a useful trade if you are comparing multiplication of, say,
>> 1024x1024 matrices with addition of those matrices.  The cost is most
>> definitely not the same.

> Indeed, but few programmable processors have instructions to deal with 
> matrices. I assume that the primitives in the O() calculations deal with 
> executable instructions.

Huh?  Are you claiming that you can't do an O() calculation if the
algorithm you are evaluating makes use of subroutines?  I beg to differ.

At the lowest level, everything reduces to executable instructions, but
that is irrelevant to what I said.  The Strassen algorithm is pointless
if you don't apply it recursively, and that is precisely where addition
and multiplication begin to have unequal cost.


-- 
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>