MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: determinant of sparse matrix

  • To: mathgroup at smc.vnet.net
  • Subject: [mg64212] Re: determinant of sparse matrix
  • From: Paul Abbott <paul at physics.uwa.edu.au>
  • Date: Mon, 6 Feb 2006 02:49:12 -0500 (EST)
  • Organization: The University of Western Australia
  • References: <ds1s8j$fse$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

In article <ds1s8j$fse$1 at smc.vnet.net>,
 Mark Fisher <mark at markfisher.net> wrote:

> Are there methods for computing the determinant of (large) sparse 
> matrices? Mathematica shuts down the kernel when I ask for
> 
> Det[iden]
> 
> where
> 
> iden = SparseArray[{i_, i_} -> 1. {10^4, 10^4}, 0.]
> 
> Of course I know the answer in this case, but more generally I'm 
> interested in the determinant of tridiagonal positive definite matrices.

A general n x n tridiagonal matrix with diagonal entries a[i], 
super-diagonal entries b[i], and sub-diagonal entries c[i], is

  tri[n_] := SparseArray[{
    {i_, i_} -> a[i], 
    {i_, j_} /; j - i == 1 -> b[i],
    {i_, j_} /; i - j == 1 -> c[j]
  }, {n, n}]

The determinant of such a matrix can be computed recursively using 
standard properties of the determinant:

  Clear[det]

  det[0] = 1;
  
  det[1] = a[1];
  
  det[n_] := det[n] = a[n] det[n-1]-b[n-1]c[n-1]det[n-2]

with no need to explicitly construct the matrix. As a check

  Simplify[ det[7] == Det[tri[7]] ]

For a large matrix you will have to increase the $RecursionLimit, say

  $RecursionLimit = 10^4

and, if the expressions for a[i], b[i], c[i], are exact, then the 
resulting expression can be huge. On the other hand, for numeric 
entries, the result is likely to be quite reasonable.

Cheers,
Paul

_______________________________________________________________________
Paul Abbott                                      Phone:  61 8 6488 2734
School of Physics, M013                            Fax: +61 8 6488 1014
The University of Western Australia         (CRICOS Provider No 00126G)    
AUSTRALIA                               http://physics.uwa.edu.au/~paul


  • Prev by Date: Using Get in a Module
  • Next by Date: Re: notebook font encoding
  • Previous by thread: determinant of sparse matrix
  • Next by thread: notebook font encoding