## Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In general, not special cases such as a triangular matrix.) Gaussian Elimination leads to O(n^3) complexity. The usual way to count operations is to count one for each «division» (by a pivot) and one for each «multiply-subtract» when you eliminate an entry.Here’s one way of […]

`What is the computational complexity of inverting an nxn matrix? (In general, not special cases such as a triangular matrix.)`

`Gaussian Elimination leads to O(n^3) complexity. The usual way to count operations is to count one for each "division" (by a pivot) and one for each "multiply-subtract" when you eliminate an entry.Here's one way of arriving at the O(n^3) result:   At the beginning, when the first row has length n, it takes n    operations to zero out any entry in the first column (one division,    and n-1 multiply-subtracts to find the new entries along the row    containing that entry. To get the first column of zeroes therefore    takes n(n-1) operations.   In the next column, we need (n-1)(n-2) operations to get the second    column zeroed out.   In the third column, we need (n-2)(n-3) operations.   The sum of all of these operations is:         n            n         n      n(n+1)(2n+1)   n(n+1)        SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------        i=1          i=1       i=1           6           2   which goes as O(n^3). To finish the operation count for Gaussian    Elimination, you'll need to tally up the operations for the process    of back-substitution (you can check that this doesn't affect the    leading order of n^3).You might think that the O(n^3) complexity is optimal, but in fact there exists a method (Strassen's method) that requires only O(n^log_2(7)) = O(n^2.807...) operations for a completely general matrix. Of course, there is a constant C in front of the n^2.807. This constant is not small (between 4 and 5), and the programming of Strassen's algorithm is so awkward, that often Gaussian Elimination is still the preferred method.Even Strassen's method is not optimal. I believe that the current record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel Winograd. Here is a Web page that discusses these methods:   Fast Parallel Matrix Multiplication - Strategies for Practical    Hybrid Algorithms - Erik Ehrlinghttp://www.f.kth.se/~f95-eeh/exjobb/background.html   These methods exploit the close relation between matrix inversion and matrix multiplication (which is also an O(n^3) task at first glance). I hope this helps! - Doctor Douglas, The Math Forumhttp://mathforum.org/dr.math/   `

## history of the universe

Uploaded on Apr 11, 2011 Backed by stunning illustrations, David Christian narrates a complete history of the universe, from the Big Bang to the Internet, in a riveting 18 minutes. This is “Big History”: an enlightening, wide-angle look at complexity, life and humanity, set against our slim share of the cosmic timeline. Uploaded on Apr 11, 2011

Backed by stunning illustrations, David Christian narrates a complete history of the universe, from the Big Bang to the Internet, in a riveting 18 minutes. This is “Big History”: an enlightening, wide-angle look at complexity, life and humanity, set against our slim share of the cosmic timeline.  Publicado el Categorías syndicated

## Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In general, not special cases such as a triangular matrix.) Gaussian Elimination leads to O(n^3) complexity. The usual way to count operations is to count one for each «division» (by a pivot) and one for each «multiply-subtract» when you eliminate an entry. Here’s one […] ```What is the computational complexity of inverting an nxn matrix? (In
general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to
count operations is to count one for each "division" (by a pivot) and
one for each "multiply-subtract" when you eliminate an entry.

Here's one way of arriving at the O(n^3) result:

At the beginning, when the first row has length n, it takes n
operations to zero out any entry in the first column (one division,
and n-1 multiply-subtracts to find the new entries along the row
containing that entry. To get the first column of zeroes therefore
takes n(n-1) operations.

In the next column, we need (n-1)(n-2) operations to get the second
column zeroed out.

In the third column, we need (n-2)(n-3) operations.

The sum of all of these operations is:

n            n         n      n(n+1)(2n+1)   n(n+1)
SUM i(i-1) = SUM i^2 - SUM i = ------------ - ------
i=1          i=1       i=1           6           2

which goes as O(n^3). To finish the operation count for Gaussian
Elimination, you'll need to tally up the operations for the process
of back-substitution (you can check that this doesn't affect the
leading order of n^3).

You might think that the O(n^3) complexity is optimal, but in fact
there exists a method (Strassen's method) that requires only
O(n^log_2(7)) = O(n^2.807...) operations for a completely general
matrix. Of course, there is a constant C in front of the n^2.807. This
constant is not small (between 4 and 5), and the programming of
Strassen's algorithm is so awkward, that often Gaussian Elimination is
still the preferred method.

Even Strassen's method is not optimal. I believe that the current
record stands at O(n^2.376), thanks to Don Coppersmith and Shmuel
Winograd. Here is a Web page that discusses these methods:

Fast Parallel Matrix Multiplication - Strategies for Practical
Hybrid Algorithms - Erik Ehrling
http://www.f.kth.se/~f95-eeh/exjobb/background.html

These methods exploit the close relation between matrix inversion and
matrix multiplication (which is also an O(n^3) task at first glance).

I hope this helps!

- Doctor Douglas, The Math Forum
http://mathforum.org/dr.math/```  ## Complexity of Matrix Inversion

What is the computational complexity of inverting an nxn matrix? (In
general, not special cases such as a triangular matrix.)

Gaussian Elimination leads to O(n^3) complexity. The usual way to
count operations is to count one for each «division» (by…

What is the computational complexity of inverting an nxn matrix? (In general, not special cases such as a triangular matrix.) Gaussian Elimination leads to O(n^3) complexity. The usual way to count operations is to count one for each "division" (by a pivot) and one for each "multiply-subtract" when you eliminate an entry. Here's one way of arriving at the O(n^3) result: At the beginning 