Package FL.ALGEBRA - Femlisp User Manual

This package defines classes for sparse matrices and methods operating on them. The interface is mostly the one used in the package FL.MATLISP extended suitably.

This module contains definitions for doing linear algebra in Femlisp and consists of several files. Besides others, these are vector.lisp and matrix.lisp, where an abstract interface for linear algebra on vectors and matrices is defined. In matlisp.lisp, this interface is realised for Matlisp matrices, and in addition the Matlisp operations are partially extended to arrays. In crs.lisp, the well-known compact row-ordered storage is defined for storing sparse matrices, and tensor.lisp and sparse-tensor.lisp contain class and method definitions for full and sparse tensors of arbitrary rank.

The file sparse.lisp then introduces a sparse storage scheme for block vectors and block matrices over arbitrary index sets. This is very convenient for functions and linear operators defined on unstructured grids because the geometric grid objects themselves can index their degrees of freedom. It also allows for local updates when advanced adaptive schemes like the one proposed in (Ruede 1993) are used.

At the moment, the classes <sparse-matrix> and <sparse-matrix> which are defined in sparse.lisp are used almost exclusively. Those classes are hash-table based, which implies that almost every index set can be used. Basic methods for those classes are also defined in sparse.lisp. An LU decomposition for <sparse-matrix> is implemented in sparselu.lisp.

Unfortunately, the use of hash-tables instead of arrays is much slower than working with, for example, compact row-ordered storage. Thus, good performance can only be expected if the inner blocks are relatively large. This is the case for systems of equations and/or approximations of higher order. Future versions of Femlisp will probably improve on that by using an array-based scheme similar to the one in sparse-tensor.lisp.

— Class: <SPARSE-MATRIX>

The <sparse-matrix> represents an unordered matrix graph indexed by general keys.
Superclasses: <MATRIX> MUTEX-MIXIN
Direct slots:

ROW-TABLE: Table of rows.
COLUMN-TABLE: Table of columns.
PRINT-ROW-KEY: Print function for row keys.
PRINT-COL-KEY: Print function for column keys.
ROW-KEY->SIZE: Function determining the number of rows of a block.
COL-KEY->SIZE: Function determining the number of columns of a block.
KEYS->PATTERN: Function determining the pattern of a block.

— Class: <SPARSE-TENSOR>

A general sparse tensor class which is implemented as a sparse vector containing full-or sparse tensor entries.
Direct slots:

RANK: Tensor rank.
INDICES: The (nonzero) indices of the first slot.
ENTRIES: The (nonzero) entries of the first slot.

— Class: <SPARSE-VECTOR>

Sparse block vector class indexed with general keys.
Superclasses: MUTEX-MIXIN
Direct slots:

BLOCKS: Table of blocks.
KEY->SIZE: Function determining the dimension of a block.
PRINT-KEY: Print function for a key.
MULTIPLICITY: Multiplicity of the sparse vector. A multiplicity different from 1 is used when handling multiple right-hand sides and solutions simultaneously.

— Function: COMBINED-PROJECTION P1 P2

Returns a projection to the range of the given projections.

— Function: CRS-MATRIX TYPE

Construct a CRS matrix with entries of type.

— Class: CRS-MATRIX

This is an abstract class crs-matrix which is made concrete by combining it with a store-vector.
Superclasses: <MATRIX>
Direct slots:

PATTERN: The pattern of the CRS matrix. This is kept separate such that the same pattern can be used for many matrices.

— Class: CRS-PATTERN

A CRS (compact row-ordered storage) pattern allowing for identification, see (Neuss 1998), for use within a crs-matrix.
Direct slots:

NROWS: Number of rows in the pattern.
NCOLS: Number of columns in the pattern.
NR-OF-ENTRIES: NIL
STORE-SIZE: NIL
ROW-STARTS: NIL
COL-INDS: NIL
OFFSETS: NIL

— Function: DIAGONAL-SPARSE-TENSOR VALUES &OPTIONAL NCOMPS

Constructs a sparse tensor of rank 2 where values are the diagonal entries. If ncomps is given then the tensor dimension is nxn with each diagonal entry being values.

— Function: EXTEND-BY-IDENTITY MAT EXTEND &KEY IGNORE (COPY T)

Extends A such that the keys in extend which are not in ignore are mapped to identity.

— Function: EXTENDED-EXTRACT ASA SKEL &KEY (ROW? T) (COL? T) &ALLOW-OTHER-KEYS

Extracts a sub-matrix from a sparse matrix.

— Function: FULL-CRS-PATTERN NROWS NCOLS

Returns trivial rectangular crs-patterns.

— Function: IN-PATTERN-P TENSOR &REST INDICES

Returns a getter/setter pair for the specified location.

— Function: INDEX-RANGE-DISJOINT-P MAT1 MAT2

Checks if the range of indices of two sparse matrices is disjoint.

— Function: LAPLACE-SPARSE-MATRIX N

Generates a sparse matrix for a 1-dimensional Laplace problem discretized with the 3-point stencil on a structured mesh.

— Function: MULTIPLICITY <ANSATZ-SPACE>

We allow multiple vectors, for solving linear problems in parallel.

— Function: RANGE-AND-DOMAIN-DISJOINT-P MAT

Checks if index range and index domain of some matrix are disjoint.

— Function: SHIFT-DIAGONAL-INVERTER ETA

Can be used for obtainint a diagonal modification to get ILU_mod.

— Function: SHIFT-PATTERN PATTERN SHIFT

shift-pattern: This function shifts a pattern to its actual offsets in the sparse graph.

— Function: SPARSE-M* A B &KEY (SPARSITY A) (JOB NN)

Sparse matrix-matrix or matrix-vector multiplication. Usually, m* should be used. But in situations, where A or B are very sparse, the complexity of this routine is much lower.

— Function: SPARSE-MATRIX->CCS A &KEY KEYS ROW-KEYS COL-KEYS RANGES ROW-RANGES COL-RANGES

Converts the sparse matrix A to CCS format. row-keys and col-keys may denote a submatrix, col-ranges and row-ranges may be used for extracting even subblocks of the entries. This is a rather difficult routine, which might suggest switching to CCS completely.

6.11 Package FL.ALGEBRA