Types

Problem{IT, FT}

Type of a sparse-matrix coupled linear algebraic equations problem.

Fields

• nrows:
  • number of rows in the matrix
  • number of elements in a row permutation
• ncols:
  • number of columns in the matrix
  • number of elements in a column permutation

Other variables:

NOTE: a user can input (i, j, v), indicating that position (i, j) in the matrix contains the value v. Or, a user can input (i, j), indicating that position (i, j) is nonzero, but not specifying a value there. Hence the distinction between "nonzeros" and "nonzero values" below.

• nnz - number of nonzero * values * in the matrix.
• dnz - number of nonzero * values * on the diagonal of the matrix.
• nedges - number of nonzeros in the matrix.
• dedges - number of nonzeros on the diagonal of the matrix.

The elements of the matrix are stored by columns using three "parallel" arrays: (link, rowsubs, values). The first element of column i stored is found in values[head[i]]. The row subscript of the element is rowsubs[head[i]]. The next element in the column is values[link[head[i]]] and so on. A zero value for link marks the end of the column.

NOTE: the elements in each column are stored in increasing order of row subscript. Some algorithms used in the package depend on this fact.

The right hand side of the matrix equation is stored in rhs, and the solution (when provided or computed) is stored in the array x. The size of the arrays is extended as required, and their lengths for not generally correspond to the number of nonzeros in the matrix: or the number of columns in the matrix.

The user can improve efficiency by providing an estimate of the number of nonzeros in the matrix - - this is done via the optional keyword parameter nnz.

Similarly, the user can improve efficiency by providing estimates for the number of rows and columns in the matrix via the optional keyword parameters nrows and ncols.

ETree{IT}

Elimination Tree type.

Used for finding and manipulating elimination trees, finding (weighted) postorderings of them, and more.

Graph{IT}

• nv - the number of vertices in the graph.
• (xadj, adj) - array pair storing the adjacency lists of the vertices.

The adjacency lists of the graph are stored in consecutive locations in the array adj. The adjacency list for the i - th vertex in the graph is stored in positions adj[k], k = xadj[i], .... xadj[i + 1] - 1.

When the graph is symmetric, if vertex i is in vertex j's adjacency vertex j is in vertex i's list. Using the representation above each edge in the graph is stored twice.

There are no self - loops (no "diagonal elements") by default. If diagonal elements are required, just input "diagonal" or "diag".

For convenience in accessing the lists, xadj is of length nv + 1, with xadj[nV + 1] = nEdges + 1. Thus, accessing vertex nv's list is the same as for any other of the vertices.

Graphs are created from Problem objects, which have a certain number of rows (nrows) and columns (ncols). These numbers are captured and stored in Graph objects as nrows and ncols as well.

Ordering{IT}

Type of ordering of the rows and columns.

• nrows is the number of rows in the matrix
• ncols is the number of columns in the matrix

Ordering objects contain two permutations and their inverses:

• rperm is a row permutation: rperm[i] = k means that the new position of row k is in position i in the new permutation.
• rinvp is a row permutation satisfying rinvp[rperm[i]] = i. Thus, rinvp[k] provides the position in the new ordering of the original row k.

cperm and cinvp are analogous to rperm and rinvp, except they apply to column permutations of the matrix.

When the matrix is symmetrically permuted, rperm = cperm and rinvp = cinvp.

• xrowblk is an array that is sometimes used to contain a partitioning of the rows of the matrix, or both the rows and columns when the matrix is symmetric.

• nrowblks is the number of blocks in the partitioning; the rows of the i - th partition are xrowblk[i], xrowblk[i] + 1 ... xrowblk[i + 1] - 1. For convenience, xrowblk has nrowblks + 1 elements, with xrowblk[nrowblks + 1] = nrows + 1.

When the matrix is not symmetric, and a partitioning of the columns is required as well, the pair (ncolblks, xcolblk) is used.

Grid(h::IT, k::IT) where {IT}

Construct a grid with a given number of spacings.