# Etiqueta: complexity

## 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 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/

## 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.

## 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…