Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
exact matrix inversion complexity

Subject: exact matrix inversion complexity

From: Balachander Narasimhan

Date: 13 Feb, 2009 02:34:01

Message: 1 of 11

Hi,

Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.

No. of divisions = n(3n-1)/2
No. of additions= No. of multiplications = n(n-1)(4n+1)/6

Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.

regs
bala

PS: The method of inversion is Gauss-Jordan

Subject: exact matrix inversion complexity

From: Darren Rowland

Date: 13 Feb, 2009 03:00:04

Message: 2 of 11

"Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <gn2m6p$kvu$1@fred.mathworks.com>...
> Hi,
>
> Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.
>
> No. of divisions = n(3n-1)/2
> No. of additions= No. of multiplications = n(n-1)(4n+1)/6
>
> Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.
>
> regs
> bala
>
> PS: The method of inversion is Gauss-Jordan

Hi Bala,
I don't think that the 'exact' number of operations is knowable, since any worthwhile implementation of Gauss-Jordan will feature pivoting, and the number of pivots will differ for different matrices.
hth
Darren

Subject: exact matrix inversion complexity

From: Balachander Narasimhan

Date: 14 Feb, 2009 21:11:01

Message: 3 of 11

hi darren,

thanks for the reply, but even the approximate computations do not consider pivoting operations. ok, lemme put the question this way? suppose, we dont do pivoting, what would be exact number of various operations involved.

regs
bala

"Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message <gn2nnk$1jv$1@fred.mathworks.com>...
> "Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <gn2m6p$kvu$1@fred.mathworks.com>...
> > Hi,
> >
> > Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.
> >
> > No. of divisions = n(3n-1)/2
> > No. of additions= No. of multiplications = n(n-1)(4n+1)/6
> >
> > Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.
> >
> > regs
> > bala
> >
> > PS: The method of inversion is Gauss-Jordan
>
> Hi Bala,
> I don't think that the 'exact' number of operations is knowable, since any worthwhile implementation of Gauss-Jordan will feature pivoting, and the number of pivots will differ for different matrices.
> hth
> Darren

Subject: exact matrix inversion complexity

From: Tim Davis

Date: 14 Feb, 2009 21:53:01

Message: 4 of 11

"Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <gn2m6p$kvu$1@fred.mathworks.com>...
> Hi,
>
> Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.
>
> No. of divisions = n(3n-1)/2
> No. of additions= No. of multiplications = n(n-1)(4n+1)/6
>
> Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.
>
> regs
> bala
>
> PS: The method of inversion is Gauss-Jordan

Im curious ... Why are you bothering to count the operations in matrix inversion, when inversion is so rarely used (or ought to be rarely used)? Do you need all the entries of the inverse? Or do you just want to count the number of operations required to solve A*x=b? The latter is roughly (2/3)n^3 for general square matrices, but drops in half if the matrix is symmetric positive definite (and Gauss-Jordan is not typically used to solve Ax=b).. This is the total number of operations, including multiplications, divisions, additions, and subtractions.

Subject: exact matrix inversion complexity

From: Steven Lord

Date: 15 Feb, 2009 18:19:23

Message: 5 of 11


"Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message
news:gn7c15$16$1@fred.mathworks.com...
> hi darren,
>
> thanks for the reply, but even the approximate computations do not
> consider pivoting operations. ok, lemme put the question this way?
> suppose, we dont do pivoting, what would be exact number of various
> operations involved.

As Tim asked ... why do you need/want to know this information?

In addition to what Tim said, let's go over a hypothetical example. What if
I were to tell you a specific algorithm took exactly m*n flops to execute?
Is that good?

...

Not necessarily. If that n*m flop algorithm requires m^7*n^6 (just a random
expression) memory accesses, even though accessing memory is fast, it's
still probably going to be, by a fairly large margin, the limiting factor in
how long (wall clock time) this algorithm takes for medium to large sized
matrices.

Read the last four paragraphs of this Cleve's Corner article, which explains
why there is no longer a FLOPS function.

http://www.mathworks.com/company/newsletters/news_notes/clevescorner/winter2000.cleve.html

--
Steve Lord
slord@mathworks.com

Subject: exact matrix inversion complexity

From: Rune Allnor

Date: 15 Feb, 2009 19:12:52

Message: 6 of 11

On 13 Feb, 03:34, "Balachander Narasimhan"
<balxxxxxch...@whatever.com> wrote:
> Hi,
>
> Most books give matrix inversion complexity with approximations and conso=
lidation of various operations like division, multiplication and addition. =
I was wondering if there was any material that gives the exact number of th=
ese operations. But I did not find any. Finally, I hand counted to arrive a=
t these expressions for a matrix of size 'n'.
>
> No. of divisions =3D n(3n-1)/2
> No. of additions=3D No. of multiplications =3D n(n-1)(4n+1)/6
>
> Is there any way to check these are correct. I did the counting based on =
the methods given in the book by Gilbert Strang on pages 15 and 45.

The book "Matrix Computations" (1996) by Golub and
van Loan contains such information. Just be aware
that the book dates from a time when multiplications
were far more expensive than additions or memory
access, so the discussions it contains might not make
all that much sense these days, when the differences
in cost of the different operations have become far
less. These days loop branching, which used to be viewed
as 'free', might actually cost as much as arithmetic
operations.

Rune

Subject: exact matrix inversion complexity

From: Balachander Narasimhan

Date: 1 Mar, 2009 19:08:01

Message: 7 of 11

Hi,

thanks for everyone who cared to reply to my query. I am sorry that I did not check the postings earlier.

Dear Tim and Steven,

Firstly, I wanted the exact complexity counts to show that an equalization algorithm I proposed requires less computation than brute-force approach. It involves multiplication and inversion of symmetric matrices. Secondly, since I work in baseband signal processing, I would imagine my algorithm being implemented on a DSP or ASIC than a general purpose processor, where divisions involve more cycles than multiplications or additions. Therefore, I wanted to give an estimate of different operations involved than just FLOPS or 'operations'.

Dear Rune,

I am not too concerned about branching complexity and such overheads. But still it is quite difficult even to get the number of multiplications involved in matrix inversion from Golub's book. I rather found it easy to obtain it from Gilbert Strang's book though it has its approximations.

regs
bala

Rune Allnor <allnor@tele.ntnu.no> wrote in message <e4e72ae4-82d4-4244-89ad-261054634410@v15g2000yqn.googlegroups.com>...
> On 13 Feb, 03:34, "Balachander Narasimhan"
> <balxxxxxch...@whatever.com> wrote:
> > Hi,
> >
> > Most books give matrix inversion complexity with approximations and conso=
> lidation of various operations like division, multiplication and addition. =
> I was wondering if there was any material that gives the exact number of th=
> ese operations. But I did not find any. Finally, I hand counted to arrive a=
> t these expressions for a matrix of size 'n'.
> >
> > No. of divisions =3D n(3n-1)/2
> > No. of additions=3D No. of multiplications =3D n(n-1)(4n+1)/6
> >
> > Is there any way to check these are correct. I did the counting based on =
> the methods given in the book by Gilbert Strang on pages 15 and 45.
>
> The book "Matrix Computations" (1996) by Golub and
> van Loan contains such information. Just be aware
> that the book dates from a time when multiplications
> were far more expensive than additions or memory
> access, so the discussions it contains might not make
> all that much sense these days, when the differences
> in cost of the different operations have become far
> less. These days loop branching, which used to be viewed
> as 'free', might actually cost as much as arithmetic
> operations.
>
> Rune

Subject: exact matrix inversion complexity

From: silva silva

Date: 27 Apr, 2009 15:17:01

Message: 8 of 11

"Tim Davis" <davis@cise.ufl.edu> wrote in message <gn7eft$akl$1@fred.mathworks.com>...
> "Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <gn2m6p$kvu$1@fred.mathworks.com>...
> > Hi,
> >
> > Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.
> >
> > No. of divisions = n(3n-1)/2
> > No. of additions= No. of multiplications = n(n-1)(4n+1)/6
> >
> > Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.
> >
> > regs
> > bala
> >
> > PS: The method of inversion is Gauss-Jordan
>
> Im curious ... Why are you bothering to count the operations in matrix inversion, when inversion is so rarely used (or ought to be rarely used)? Do you need all the entries of the inverse? Or do you just want to count the number of operations required to solve A*x=b? The latter is roughly (2/3)n^3 for general square matrices, but drops in half if the matrix is symmetric positive definite (and Gauss-Jordan is not typically used to solve Ax=b).. This is the total number of operations, including multiplications, divisions, additions, and subtractions.

Dear Tim,

But ths number (2/3)n^3 ? for real matrix right? For the case when matrix A is complex, do you know which is the aditional complexity?

Subject: exact matrix inversion complexity

From: Balachander Narasimhan

Date: 27 Apr, 2009 15:45:03

Message: 9 of 11

A complex matrix would require (2/3)n^3 complex operations and each complex operation could be mapped to a corresponding number of real operations. The other possibility is you can write the real equivalent of matrix A as follows

A_req=[real(A) -imag(A);imag(A) real(A)]

If A was of size nxn, then A_req is of size 2nx2n. Therefore the complexity of inversion is (2/3)(2n)^3

regs
bala

"silva silva" <asilva@av.it.pt> wrote in message <gt4i9d$ebg$1@fred.mathworks.com>...
> "Tim Davis" <davis@cise.ufl.edu> wrote in message <gn7eft$akl$1@fred.mathworks.com>...
> > "Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote in message <gn2m6p$kvu$1@fred.mathworks.com>...
> > > Hi,
> > >
> > > Most books give matrix inversion complexity with approximations and consolidation of various operations like division, multiplication and addition. I was wondering if there was any material that gives the exact number of these operations. But I did not find any. Finally, I hand counted to arrive at these expressions for a matrix of size 'n'.
> > >
> > > No. of divisions = n(3n-1)/2
> > > No. of additions= No. of multiplications = n(n-1)(4n+1)/6
> > >
> > > Is there any way to check these are correct. I did the counting based on the methods given in the book by Gilbert Strang on pages 15 and 45.
> > >
> > > regs
> > > bala
> > >
> > > PS: The method of inversion is Gauss-Jordan
> >
> > Im curious ... Why are you bothering to count the operations in matrix inversion, when inversion is so rarely used (or ought to be rarely used)? Do you need all the entries of the inverse? Or do you just want to count the number of operations required to solve A*x=b? The latter is roughly (2/3)n^3 for general square matrices, but drops in half if the matrix is symmetric positive definite (and Gauss-Jordan is not typically used to solve Ax=b).. This is the total number of operations, including multiplications, divisions, additions, and subtractions.
>
> Dear Tim,
>
> But ths number (2/3)n^3 ? for real matrix right? For the case when matrix A is complex, do you know which is the aditional complexity?

Subject: exact matrix inversion complexity

From: Tim Davis

Date: 14 May, 2009 21:51:01

Message: 10 of 11

"Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote
> Dear Tim and Steven,
>
> Firstly, I wanted the exact complexity counts to show that an equalization algorithm I proposed requires less computation than brute-force approach. It involves multiplication and inversion of symmetric matrices. Secondly, since I work in baseband signal processing, I would imagine my algorithm being implemented on a DSP or ASIC than a general purpose processor, where divisions involve more cycles than multiplications or additions. Therefore, I wanted to give an estimate of different operations involved than just FLOPS or 'operations'.


If you are multiplying by the inverse of a symmetric matrix, then you are doing the wrong thing - whether you are using a standard CPU or a DSP. Multiplying by the inverse is slower and less accurate than solving a linear system. Never ever EVER multiply anything by the inverse of a matrix.

If the matrix A is symmetric positive definite, x =A\b takes about (1/3)*n^3 operations. The naive x=inv(A)*b takes many times more than that and is less accurate as well.

Or perhaps I've misunderstood -- are you saying the brute-force method uses x=inv(A)*b? I doubt that it does, even so. Many times people will write x=inv(A)*b mathematically, when they mean full well to solve the linear system A*x=b. In that case, it's still fairest to the brute-force method to count the flops for x=A\b, not x=inv(A)*b, which no one would ever do.

Subject: exact matrix inversion complexity

From: Balachander Narasimhan

Date: 17 May, 2009 19:31:01

Message: 11 of 11

Dear Tim,

thanks for the response. I do not have algorithms or DSP expertise. Your suggestions do make a lot of sense to me. I think I should compute the complexity of solving an equation than matrix inverse.

regs
bala

"Tim Davis" <davis@cise.ufl.edu> wrote in message <gui3o5$6n4$1@fred.mathworks.com>...
> "Balachander Narasimhan" <balxxxxxchand@whatever.com> wrote
> > Dear Tim and Steven,
> >
> > Firstly, I wanted the exact complexity counts to show that an equalization algorithm I proposed requires less computation than brute-force approach. It involves multiplication and inversion of symmetric matrices. Secondly, since I work in baseband signal processing, I would imagine my algorithm being implemented on a DSP or ASIC than a general purpose processor, where divisions involve more cycles than multiplications or additions. Therefore, I wanted to give an estimate of different operations involved than just FLOPS or 'operations'.
>
>
> If you are multiplying by the inverse of a symmetric matrix, then you are doing the wrong thing - whether you are using a standard CPU or a DSP. Multiplying by the inverse is slower and less accurate than solving a linear system. Never ever EVER multiply anything by the inverse of a matrix.
>
> If the matrix A is symmetric positive definite, x =A\b takes about (1/3)*n^3 operations. The naive x=inv(A)*b takes many times more than that and is less accurate as well.
>
> Or perhaps I've misunderstood -- are you saying the brute-force method uses x=inv(A)*b? I doubt that it does, even so. Many times people will write x=inv(A)*b mathematically, when they mean full well to solve the linear system A*x=b. In that case, it's still fairest to the brute-force method to count the flops for x=A\b, not x=inv(A)*b, which no one would ever do.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us