Home · Pages · Index · Overviews

Band_Factor Class Reference

A sparse LU decompositions of tri- and penta-diagonal matrices. More...

 #include <linear.algebra.h>

Routines

Band_Factor * Triband_DecomposeG (Double_Matrix *t)
Double_Vector * Triband_Solve (Double_Vector *v RM, Band_Factor *f)

Band_Factor * Spline_DecomposeG (Dimn_Type n, boolean closed)
Double_Vector * Spline_Slopes (Double_Vector *v RM, Band_Factor *f)

Band_Factor * Pentaband_DecomposeG (Double_Matrix *p)
Double_Vector * Pentaband_Solve (Double_Vector *v RM, Band_Factor *f)

Detailed Description

Tri- and penta-diagonal systems, including cyclic systems, occur naturally in many problem contexts. For example computing a cubic spline through a set of points involves solving a tri-diagonal system, and updating an active contour or snake involves solving a penta-diagonal system. A Band_Factor object encodes a specialized LU decomposition of a direct or cyclic, tri- or penta-diagonal system that once computed allows one to then solve such systems particularly efficiently. Triband_Decompose generates a Band_Factor object that models the decomposition of a tri-diagonal system of equations that can then be given to Triband_Solve to solve the system for any particular constraint conditions. Finding the slope vectors for a C0-, C1-, and C2-continuous, open or closed spline through a set of points involves solving a particular tri-diagonal system whose Band_Factor decomposition for a particular number of points n is generated by Spline_Decompose. This Band_Factor can then be used to compute slopes for a particular set of points with Spline_Slopes. Finally, Pentaband_Decompose and Pentaband_Solve are the penta-diagonal analogs to the tri-diagonal routines just described.


Routine Documentation

Band_Factor * Triband_DecomposeG (Double_Matrix *t)

Produces an optimized LU decomposition of a tri-diagonal system [ a b c ] where t is a 3 x n matrix where t[0] = a, t[1] = b, and t[2] = c. If the system is singular a NULL pointer is returned. The system is circular if a[0] ≠ 0 or c[n-1] ≠ 0. The routine handles this case, albeit somewhat less efficiently than the non-circular case.

Double_Vector * Triband_Solve (Double_Vector *v RM, Band_Factor *f)

Solves the system [ a b c ] x = v in place within v, for the tri-diagonal matrix [ a b c ] encoded in the Band_Factor object f. Note that f is not modified and so the same system can be solved repeatedly with different values of v.

Band_Factor * Spline_DecomposeG (Dimn_Type n, boolean closed)

Generate a Band_Factor object modeling the special special system of equations that determine the unique slopes of the 2nd-derivative continuous cubic spline that passes through n points. The boolean close should be true if a closed curve is desired, and false if the curve is on open one ending at the first and last points.

Double_Vector * Spline_Slopes (Double_Vector *v RM, Band_Factor *f)

Given the coordinate (in a particular dimension) of n points in a vector v and the Band_Factor object f for this number of points, replace the values in v with the displacement of the slopes at each point in the given dimension. For example, in 3D one would solve the system three times in order to get the x-, y-, and z-displacments of the slope vectors, by giving the x-, y-, and z-coordinates of the n points in question.

Band_Factor * Pentaband_DecomposeG (Double_Matrix *p)

Produces an optimized LU decomposition of a penta-diagonal system [ a b c d e ] where t is a 5 x n matrix where t[0] = a, t[1] = b, t[2] = c., t[3] = d, and t[4] = e. If the system is singular a NULL pointer is returned. The system is circular if any of a[0], a[1], d[n-1], e[n-2], or e[n-1] are not zero. The routine handles this case, albeit somewhat less efficiently than the non-circular case.

Double_Vector * Pentaband_Solve (Double_Vector *v RM, Band_Factor *f)

Solves the system [ a b c d e ] x = v in place within v, for the penta-diagonal matrix [ a b c d e ] encoded in the Band_Factor object f. Note that f is not modified and so the same system can be solved repeatedly with different values of v.