       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 = 1;

det = a;

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 == Det[tri] ]

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