smile.math.matrix

Class BandMatrix

java.lang.Object

smile.math.matrix.Matrix

smile.math.matrix.BandMatrix

All Implemented Interfaces:

java.io.Serializable, LinearSolver

public class BandMatrix
extends Matrix
implements LinearSolver

A band matrix is a sparse matrix, whose non-zero entries are confined to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.

In numerical analysis, matrices from finite element or finite difference problems are often banded. Such matrices can be viewed as descriptions of the coupling between the problem variables; the bandedness corresponds to the fact that variables are not coupled over arbitrarily large distances. Such matrices can be further divided - for instance, banded matrices exist where every element in the band is nonzero. These often arise when discretizing one-dimensional problems. Problems in higher dimensions also lead to banded matrices, in which case the band itself also tends to be sparse. For instance, a partial differential equation on a square domain (using central differences) will yield a matrix with a half-bandwidth equal to the square root of the matrix dimension, but inside the band only 5 diagonals are nonzero. Unfortunately, applying Gaussian elimination (or equivalently an LU decomposition) to such a matrix results in the band being filled in by many non-zero elements. As sparse matrices lend themselves to more efficient computation than dense matrices, there has been much research focused on finding ways to minimize the bandwidth (or directly minimize the fill in) by applying permutations to the matrix, or other such equivalence or similarity transformations.

From a computational point of view, working with band matrices is always preferential to working with similarly dimensioned dense square matrices. A band matrix can be likened in complexity to a rectangular matrix whose row dimension is equal to the bandwidth of the band matrix. Thus the work involved in performing operations such as multiplication falls significantly, often leading to huge savings in terms of calculation time and complexity.

Given a n-by-n band matrix with m₁ rows below the diagonal and m₂ rows above. The matrix is compactly stored in an array A[0,n-1][0,m₁+m₂]. The diagonal elements are in A[0,n-1][m₁]. Subdiagonal elements are in A[j,n-1][0,m₁-1] with j > 0 appropriate to the number of elements on each subdiagonal. Superdiagonal elements are in A[0,j][m₁+1,m₂+m₂] with j < n-1 appropriate to the number of elements on each superdiagonal.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
BandMatrix(int n, int m) Constructor of an n-by-n band-diagonal matrix A with m subdiagonal rows and m superdiagonal rows.
BandMatrix(int n, int m1, int m2) Constructor of an n-by-n band-diagonal matrix A with m1 subdiagonal rows and m2 superdiagonal rows.

Method Summary

Modifier and Type	Method and Description
BandMatrix	aat() Returns A * A'
BandMatrix	ata() Returns A' * A
double[]	atx(double[] x, double[] y) y = A' * x
double[]	atxpy(double[] x, double[] y) y = A' * x + y
double[]	atxpy(double[] x, double[] y, double b) y = A' * x + b * y
double[]	ax(double[] x, double[] y) y = A * x
double[]	axpy(double[] x, double[] y) y = A * x + y
double[]	axpy(double[] x, double[] y, double b) y = A * x + b * y
void	decompose() LU decomposition.
double	det() Returns the matrix determinant.
double[]	diag() Returns the diagonal elements.
double	get(int i, int j) Returns the entry value at row i and column j.
void	improve(double[] b, double[] x) Iteratively improve a solution to linear equations.
int	ncols() Returns the number of columns.
int	nrows() Returns the number of rows.
BandMatrix	set(int i, int j, double x)
double[]	solve(double[] b, double[] x) Solve A*x = b.
BandMatrix	transpose() Returns the matrix transpose.

Methods inherited from class smile.math.matrix.Matrix

apply, diag, eigen, eigen, eye, eye, isSymmetric, newInstance, newInstance, newInstance, ones, randn, randn, setSymmetric, svd, svd, toString, toString, trace, zeros

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BandMatrix

public BandMatrix(int n,
                  int m)

Constructor of an n-by-n band-diagonal matrix A with m subdiagonal rows and m superdiagonal rows.

Parameters:

n - the dimensionality of matrix.

m - the number of subdiagonal and superdiagonal rows.

BandMatrix

public BandMatrix(int n,
                  int m1,
                  int m2)

Constructor of an n-by-n band-diagonal matrix A with m₁ subdiagonal rows and m₂ superdiagonal rows.

Parameters:

n - the dimensionality of matrix.

m1 - the number of subdiagonal rows.

m2 - the number of superdiagonal rows.

Method Detail

nrows

public int nrows()

Description copied from class: Matrix

Returns the number of rows.

Specified by:

nrows in class Matrix

ncols

public int ncols()

Description copied from class: Matrix

Returns the number of columns.

Specified by:

ncols in class Matrix

get

public double get(int i,
                  int j)

Description copied from class: Matrix

Returns the entry value at row i and column j.

Specified by:

get in class Matrix

set

public BandMatrix set(int i,
                      int j,
                      double x)

transpose

public BandMatrix transpose()

Returns the matrix transpose.

Specified by:

transpose in class Matrix

Returns:

the transpose of matrix.

ata

public BandMatrix ata()

Description copied from class: Matrix

Returns A' * A

Specified by:

ata in class Matrix

aat

public BandMatrix aat()

Description copied from class: Matrix

Returns A * A'

Specified by:

aat in class Matrix

det

public double det()

Returns the matrix determinant.

decompose

public void decompose()

LU decomposition.

ax

public double[] ax(double[] x,
                   double[] y)

Description copied from class: Matrix

y = A * x

Specified by:

ax in class Matrix

Returns:

y

axpy

public double[] axpy(double[] x,
                     double[] y)

Description copied from class: Matrix

y = A * x + y

Specified by:

axpy in class Matrix

Returns:

y

axpy

public double[] axpy(double[] x,
                     double[] y,
                     double b)

Description copied from class: Matrix

y = A * x + b * y

Specified by:

axpy in class Matrix

Returns:

y

atx

public double[] atx(double[] x,
                    double[] y)

Description copied from class: Matrix

y = A' * x

Specified by:

atx in class Matrix

Returns:

y

atxpy

public double[] atxpy(double[] x,
                      double[] y)

Description copied from class: Matrix

y = A' * x + y

Specified by:

atxpy in class Matrix

Returns:

y

atxpy

public double[] atxpy(double[] x,
                      double[] y,
                      double b)

Description copied from class: Matrix

y = A' * x + b * y

Specified by:

atxpy in class Matrix

Returns:

y

diag

public double[] diag()

Description copied from class: Matrix

Returns the diagonal elements.

Overrides:

diag in class Matrix

solve

public double[] solve(double[] b,
                      double[] x)

Solve A*x = b.

Specified by:

solve in interface LinearSolver

Parameters:

b - a vector with as many rows as A.

x - is output vector so that L*U*X = b(piv,:)

Returns:

the solution vector x

Throws:

java.lang.RuntimeException - if matrix is singular.

improve

public void improve(double[] b,
                    double[] x)

Iteratively improve a solution to linear equations.

Parameters:

b - right hand side of linear equations.

x - a solution to linear equations.