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