iconEuler Reference

Large and Sparse Matrices

Routines for large, thin matrices, and for incidence matrices.

See also the functions in the Euler core.

To solve large, sparse equations the CG-method implemented in cgX or cpxfit is the method of choice. The function cpxfit uses the normal equation to fit Ax-b. The Gauß-Seidel method seidelX is an alternative for diagonal dominant matrices.

Gauß-Seidel

function seidelX (H:cpx, b:real column, x:column=0, ..
    om:real positive scalar=1.2)

  Solve Hx=b using the Gauß-Seidel method for compressed matrices H.
  
  The Gauß-Seidel method  with Relaxation is an iterative method,
  which converges for all positive definite matrices. For large
  matrices, it may work well. However, the conjugate gradient method
  "cgX" is the method of choice.
  
  H must be diagonal dominant, at least not have 0 on the diagonal.
  om is the relaxation parameter between 1 and 2. x is start value
  (automatic if 0). It is possible to specify the accuracy with
  eps=...
  
  H : compressed matrix (nxm)
  b : column vector (mx1)
  om : optional relaxation coefficient
  
  Returns the solution x, a column vector.
  
  See: 
cgX (Large and Sparse Matrices),
seidel (Linear Algebra)
function cgX (H:cpx, b:real column, x0:real column=none, f:index=10)

  Conjugate gradient method to solve Hx=b for compressed H.
  
  This is the method of choice for large, sparse matrices. In most
  cases, it will work well, fast, and accurate.
  
  H must be positive definite. Use cpxfit, if it is not.
  
  The accuarcy can be controlled with an additional parameter
  eps. The algorithm stops, when the error gets smaller then eps, or
  after f*n iterations, if the error gets larger. x0 is an optional
  start vector.
  
  H : compressed matrix (nxm)
  b : column vector (mx1)
  x0 : optional start point (mx1)
  f : number of steps, when the method should be restarted
  
  See: 
cpxfit (Large and Sparse Matrices),
cg (Linear Algebra),
cgXnormal (Large and Sparse Matrices)
function cgXnormal (H:cpx, Ht:cpx, b:real column, x0:real column=none, ..
    f:index=10)

  Conjugate gradient method to solve Ht.H.x=Ht.b for compressed H.
  
  This algorithm is used by cpxfit to solve the normal equation
  H'Hx=H'b, which minimizes |Hx-b|, i.e., to find an optimal solution
  of an linear system with more equations than unknowns.
  
  Stops, when the error gets smaller then eps, or after f*n
  iterations, when the error gets larger. x0 is an optional start
  vector.
  
  H : compressed matrix (nxm)
  Ht : compressed matrix (mxn)
  b : column vector (mx1)
  x0 : optional start (mx1)
  f : number of steps, when the method should be restarted
  
  See: 
cpxfit (Large and Sparse Matrices)
function cpxfit (H:cpx, b:real column, f:index=10)

  Minimize |Hx-b| for a compressed matrix H.
  
  This function uses the conjugate gradient method to solve the
  normal equation H'Hx=H'b for sparse compressed matrices H.
  
  H : compressed matrix (nxm)
  b : column vector (mx1)
  f : number of steps, when the method should be restarted
  
  See: 
fit (Linear Algebra),
fitnormal (Linear Algebra),
svdsolve (Linear Algebra)

Utility Functions

Some utility functions for the compressed matrix format.

function cpxsetdiag (R:cpx, k:integer scalar, d:real vector)

  Set the k-th diagonal of the compressed matrix R to the value d.
  
  k=0 is the main diagonal, k=-1 the diagonal below, and k=1 the
  diagonal above.
  
  Note that this function does not change R, but returns a new matrix
  with the changes.
  
  See: 
setdiag (Euler Core)
function cpxmultrows (c:real column, A:cpx)

  Multiply the i-th row of the compressed matrix A by c[i].
  
  Note that this function does not change R, but returns a new matrix
  with the changes.
  
  c : column vector (nx1)
  A : compressed matrix (nxm)
  
  See: 
cpxsetrow (Large and Sparse Matrices)
function cpxsetrow (A:cpx, i:index, r:real vector)

  Set the i-th row of the compressed matrix A to r.
  
  Note that this function does not change R, but returns a new matrix
  with the changes.
  
  A : compressed matrix (nxm)
  i : index
  r : row vector (1xm)
  
function cpxsetcolumn (A:cpx, j:index, c:real column)

  Set the j-th column of the compressed matrix A to c.
  
  Note that this function does not change R, but returns a new matrix
  with the changes.
  
  A : compressed matrix (nxm)
  j : integer
  c : column vector (mx1)
  
  See: 
cpxsetrow (Large and Sparse Matrices)
function cpxsum (A:cpx)

  The sums of all rows of the compressed matrix A.
  
  See: 
sum (Euler Core),
sum (Maxima Documentation)

Incidence Matrices

function rectangleIncidenceX (n:index, m:index)

  Incidence matrix of a rectangle grid in compact form.
  
  The incidence matrix of a graph is the matrix H, such that H(i,j)
  contains 1, if node i is connected to node j. In this function, the
  graph consists of the points of a rectangle, and the edges connect
  adjactant points. The points in the rectangle are numbered row by
  row.
  
  Returns a compressed nm x nm matrix.
  
  See: 
cpxset (Euler Core)

Documentation Homepage