Sparse matrices

A sparse real matrix, in triplet or column-compressed form.

typedef struct og_sparsemat_t { og_sparsemat_type_t type; og_int_t nrow; og_int_t ncol; og_int_t nnz; og_int_t cap; og_int_t *row; og_int_t *col; og_real_t *val; } og_sparsemat_t;

Indices are zero-based. Both forms keep nnz stored entries in row and val; a position may be stored more than once (its value is the sum of the pieces) and stored values may be zero. Triplet: entry k is (row[k], col[k], val[k]), easy to extend with sparsemat_entry. Column-compressed: column j holds entries col[j] .. col[j+1]-1, col has ncol + 1 elements and col[ncol] is the number of entries. cap is the room for entries. Read the fields if you like, but change the matrix only through the functions.

Checked

Unit tests.

C name

og_sparsemat_t

In notebooks

Og.Sparsemat

igraph 1.0

igraph_sparsemat_t

See also

sparsemat_init, sparsemat_compress, sparsemat_type_t

The two layouts of a sparse matrix.

typedef enum og_sparsemat_type_t { OG_SPARSEMAT_TRIPLET = 0, OG_SPARSEMAT_CC = 1 } og_sparsemat_type_t;

OG_SPARSEMAT_TRIPLET (0): a list of (row, column, value) entries. OG_SPARSEMAT_CC (1): entries grouped column by column (compressed sparse column).

Checked

Unit tests.

C name

og_sparsemat_type_t

In notebooks

Og.SparsematType

igraph 1.0

igraph_sparsemat_type_t

See also

sparsemat_type, sparsemat_compress

An iterator over the stored entries of a sparse matrix.

typedef struct og_sparsemat_iterator_t { const og_sparsemat_t *mat; og_int_t pos; og_int_t col; } og_sparsemat_iterator_t;

Holds the matrix, the current position in the storage arrays and, for a column-compressed matrix, the current column. Set it up with sparsemat_iterator_init; it owns no memory.

Checked

Unit tests.

C name

og_sparsemat_iterator_t

In notebooks

Og.SparsematIterator

igraph 1.0

igraph_sparsemat_iterator_t

See also

sparsemat_iterator_init, sparsemat_iterator_next

The result of a symbolic analysis (sparsemat_symblu or sparsemat_symbqr).

typedef struct og_sparsemat_symbolic_t { int kind; og_bool_t transposed; og_int_t nrow; og_int_t ncol; og_int_t *colorder; og_int_t *tree; og_int_t *rowslot; og_int_t *firstcol; og_int_t slots; og_real_t est_lower; og_real_t est_upper; } og_sparsemat_symbolic_t;

Opaque: pass it to sparsemat_lu / sparsemat_luresol or sparsemat_qr / sparsemat_qrresol, then free it with sparsemat_symbolic_destroy. It holds the column order and, for QR, the column elimination tree and the factor row of every matrix row.

Checked

Unit tests.

C name

og_sparsemat_symbolic_t

In notebooks

Og.SparsematSymbolic

igraph 1.0

igraph_sparsemat_symbolic_t

See also

sparsemat_symblu, sparsemat_symbqr, sparsemat_symbolic_destroy

The result of a numeric factorization (sparsemat_lu or sparsemat_qr).

typedef struct og_sparsemat_numeric_t { int kind; og_sparsemat_t L; og_sparsemat_t U; og_real_t *diag; og_int_t *rowstep; og_real_t *tau; } og_sparsemat_numeric_t;

Opaque: pass it to sparsemat_luresol or sparsemat_qrresol, then free it with sparsemat_numeric_destroy. LU: P A Q = L U with L's multipliers below a unit diagonal, U's entries above its diagonal, U's diagonal in diag and each row's pivot step in rowstep. QR: the reflection vectors in L, their coefficients in tau, R's off-diagonal entries in U and R's diagonal in diag.

Checked

Unit tests.

C name

og_sparsemat_numeric_t

In notebooks

Og.SparsematNumeric

igraph 1.0

igraph_sparsemat_numeric_t

See also

sparsemat_lu, sparsemat_qr, sparsemat_numeric_destroy

Which factorization sparsemat_arpack_rssolve uses for the shifted system in mode 3.

typedef enum og_sparsemat_solve_t { OG_SPARSEMAT_SOLVE_LU = 0, OG_SPARSEMAT_SOLVE_QR = 1 } og_sparsemat_solve_t;

OG_SPARSEMAT_SOLVE_LU (0) or OG_SPARSEMAT_SOLVE_QR (1).

Checked

Unit tests.

C name

og_sparsemat_solve_t

In notebooks

Og.SparsematSolve

igraph 1.0

igraph_sparsemat_solve_t

See also

sparsemat_arpack_rssolve

Initialises a sparse matrix and registers it on the cleanup stack in one step.

#define OG_SPARSEMAT_INIT_FINALLY(A, rows, cols, nzmax) do { OG_CHECK(og_sparsemat_init((A), (rows), (cols), (nzmax))); OG_FINALLY(og_sparsemat_destroy, (A)); } while (0)

Inside a function that returns error_t: if sparsemat_init fails the error is passed on; otherwise sparsemat_destroy is registered so that a later error frees the matrix. On success destroy it yourself and pop the entry with OG_FINALLY_CLEAN(1).

Parameters

• A Pointer to the matrix.
• rows Number of rows.
• cols Number of columns.
• nzmax Room for entries.

Returns

Returns from the enclosing function with the error code when the initialisation fails.

Complexity

As sparsemat_init.

Checked

Unit tests.

C name

OG_SPARSEMAT_INIT_FINALLY

See also

sparsemat_init, sparsemat_destroy

Creates an empty sparse matrix in triplet form, ready for entries.

og_error_t og_sparsemat_init(
    og_sparsemat_t *A,
    og_int_t rows,
    og_int_t cols,
    og_int_t nzmax
);

The new rows by cols matrix stores nothing yet and has room for nzmax entries. Add entries with sparsemat_entry; the room grows by itself when it runs out. Most arithmetic, the solvers and the eigenvalue functions need the column-compressed form, so convert with sparsemat_compress when the matrix is complete. Free it with sparsemat_destroy.

Indices are zero-based. A position may be given more than once; its value is then the sum of the pieces (see sparsemat_dupl).

Parameters

• A The matrix to initialise; not initialised yet.
• rows Number of rows, 0 or more.
• cols Number of columns, 0 or more.
• nzmax Initial room for entries, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL rows, cols or nzmax is negative, or cols is too large.
• OG_ENOMEM Not enough memory.

Complexity

O(1) apart from the allocation of nzmax entries.

Checked

python-igraph exposes no sparse-matrix API; the 220 random fixture matrices of the sparse tests are built with init and entry; negative sizes unit-tested.

C name

og_sparsemat_init

In notebooks

Og.Native.og_sparsemat_init

igraph 1.0

igraph_sparsemat_init

See also

sparsemat_entry, sparsemat_compress, sparsemat_destroy, SPARSEMAT_INIT_FINALLY

og_sparsemat_t T, A;
og_vector_t x, y;
og_sparsemat_init(&T, 2, 3, 4);        /* 2 x 3, triplet form */
og_sparsemat_entry(&T, 0, 0, 1.0);
og_sparsemat_entry(&T, 1, 2, 4.0);
og_sparsemat_entry(&T, 1, 2, 1.0);     /* a second piece: (1, 2) is now 5 */
og_sparsemat_compress(&T, &A);         /* A: new, column-compressed */
og_vector_init(&x, 3);
og_vector_fill(&x, 1.0);
og_vector_init(&y, 2); /* zeros */
og_sparsemat_gaxpy(&A, &x, &y);        /* y += A x: (1, 5) */
og_vector_destroy(&y);
og_vector_destroy(&x);
og_sparsemat_destroy(&A);
og_sparsemat_destroy(&T);

Creates a new sparse matrix holding a copy of another.

og_error_t og_sparsemat_init_copy(
    og_sparsemat_t *to,
    const og_sparsemat_t *from
);

The copy has the same layout (triplet or column-compressed), the same stored entries in the same order and the same room for entries. to must not be initialised yet.

Parameters

• to The new matrix; not initialised yet.
• from The matrix to copy.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + ncol).

Checked

python-igraph exposes no sparse-matrix API; unit tests of layout, entries and room.

C name

og_sparsemat_init_copy

In notebooks

Og.Native.og_sparsemat_init_copy

igraph 1.0

igraph_sparsemat_init_copy

See also

sparsemat_init, sparsemat_destroy

Creates a square diagonal sparse matrix from a vector of diagonal values.

og_error_t og_sparsemat_init_diag(
    og_sparsemat_t *A,
    og_int_t nzmax,
    const og_vector_t *values,
    og_bool_t compress
);

The matrix is n by n with n = size(values), and values[k] is stored at (k, k). Every value is stored, zeros included. With compress true the result is column-compressed, otherwise in triplet form. nzmax is the room for entries; a value below n is raised to n.

Parameters

• A The matrix to initialise; not initialised yet.
• nzmax Room for entries; at least n is used.
• values The diagonal.
• compress true: column-compressed form; false: triplet form.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL nzmax is negative.
• OG_ENOMEM Not enough memory.

Complexity

O(n).

Checked

python-igraph exposes no sparse-matrix API; unit tests in both layouts.

C name

og_sparsemat_init_diag

In notebooks

Og.Native.og_sparsemat_init_diag

igraph 1.0

igraph_sparsemat_init_diag

See also

sparsemat_init_eye, sparsemat_init

Creates an n by n sparse matrix with the same value on every diagonal position.

og_error_t og_sparsemat_init_eye(
    og_sparsemat_t *A,
    og_int_t n,
    og_int_t nzmax,
    og_real_t value,
    og_bool_t compress
);

value is stored at (k, k) for k = 0 .. n-1 (also when it is 0). With value 1 this is the identity matrix. compress chooses column-compressed (true) or triplet form (false). nzmax below n is raised to n.

Parameters

• A The matrix to initialise; not initialised yet.
• n Size, 0 or more.
• nzmax Room for entries; at least n is used.
• value The diagonal value.
• compress true: column-compressed form; false: triplet form.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL n or nzmax is negative.
• OG_ENOMEM Not enough memory.

Complexity

O(n).

Checked

python-igraph exposes no sparse-matrix API; unit tests in both layouts.

C name

og_sparsemat_init_eye

In notebooks

Og.Native.og_sparsemat_init_eye

igraph 1.0

igraph_sparsemat_init_eye

See also

sparsemat_init_diag

Changes the room a sparse matrix has for entries.

og_error_t og_sparsemat_realloc(og_sparsemat_t *A, og_int_t nzmax);

The room becomes nzmax, but never less than the number of entries already stored, so nothing is lost. Use it to trim spare room or to reserve room before many sparsemat_entry calls.

Parameters

• A The sparse matrix.
• nzmax The room wanted, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL nzmax is negative.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz) for the copy.

Checked

python-igraph exposes no sparse-matrix API; unit tests.

C name

og_sparsemat_realloc

In notebooks

Og.Native.og_sparsemat_realloc

igraph 1.0

igraph_sparsemat_realloc

See also

sparsemat_nonzero_storage, sparsemat_entry

Frees the storage of a sparse matrix.

void og_sparsemat_destroy(og_sparsemat_t *A);

Destroying twice is harmless, and so is a NULL pointer.

Parameters

• A The matrix, or NULL.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests (double destroy, out-of-memory runs).

C name

og_sparsemat_destroy

In notebooks

Og.Native.og_sparsemat_destroy

igraph 1.0

igraph_sparsemat_destroy

See also

sparsemat_init

Extracts a submatrix with chosen rows and columns.

og_error_t og_sparsemat_index(
    const og_sparsemat_t *A,
    const og_vector_int_t *p,
    const og_vector_int_t *q,
    og_sparsemat_t *res,
    og_real_t *constres
);

res(k, l) = A(p[k], q[l]). p and q may repeat indices and come in any order; NULL selects all rows or all columns in order. The result is a new column-compressed matrix with the pieces of each position summed; inside each column the rows follow A's storage order (sparsemat_sort sorts them).

If constres is not NULL it receives the value of the first non-zero element of the selection (smallest column, then smallest row), or 0 when there is none: handy when a single element is selected. res may be NULL when only constres is wanted.

Parameters

• A The sparse matrix, in column-compressed form.
• p Row indices, or NULL for all rows.
• q Column indices, or NULL for all columns.
• res The result; not initialised yet. May be NULL.
• constres Receives the first non-zero element, or NULL.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, or an index in p or q is out of range.
• OG_EOVERFLOW The selection would hold more entries than og_int_t can count.
• OG_ENOMEM Not enough memory.

Complexity

O(nrow + size(p) + size(q) + entries of the selected columns + entries of the result).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy's A[ix_(p, q)] on 220 matrices x 4 selections, repeats and NULL included.

C name

og_sparsemat_index

In notebooks

Og.Native.og_sparsemat_index

igraph 1.0

igraph_sparsemat_index

See also

sparsemat_permute, sparsemat_get

Adds one entry to a sparse matrix in triplet form.

og_error_t og_sparsemat_entry(
    og_sparsemat_t *A,
    og_int_t row,
    og_int_t col,
    og_real_t elem
);

Appends the piece (row, col, elem). If the position already has pieces, they add up. An entry outside the current shape enlarges the matrix to include it. The room grows automatically (doubling).

Parameters

• A The matrix, in triplet form.
• row Row index, 0 or more.
• col Column index, 0 or more.
• elem The value.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is column-compressed, or an index is negative or too large.
• OG_ENOMEM Not enough memory.

Complexity

Amortised O(1).

Checked

python-igraph exposes no sparse-matrix API; unit tests; every fixture matrix is built through it.

C name

og_sparsemat_entry

In notebooks

Og.Native.og_sparsemat_entry

igraph 1.0

igraph_sparsemat_entry

See also

sparsemat_init, sparsemat_compress

Keeps only the stored entries a callback function accepts.

og_error_t og_sparsemat_fkeep(
    og_sparsemat_t *A,
    og_int_t (*fkeep)(og_int_t, og_int_t, og_real_t, void *),
    void *other
);

Calls fkeep(row, col, value, other) for every stored piece in storage order and keeps the piece when the callback returns non-zero. The matrix is compacted in place; its room is not changed.

Parameters

• A The sparse matrix, in column-compressed form.
• fkeep The filter: returns non-zero to keep an entry.
• other Passed through to the filter as its last argument.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, or fkeep is NULL.

Complexity

O(nnz + ncol) plus the callback calls.

Checked

Unit tests.

C name

og_sparsemat_fkeep

In notebooks

Og.Native.og_sparsemat_fkeep

igraph 1.0

igraph_sparsemat_fkeep

See also

sparsemat_dropzeros, sparsemat_droptol

Removes the elements that are exactly zero.

og_error_t og_sparsemat_dropzeros(og_sparsemat_t *A);

The pieces of each position are summed first (as sparsemat_dupl does), so a pair of pieces 2 and -2 is removed as the zero it is. NaN values are kept.

Parameters

• A The sparse matrix, in column-compressed form.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not in column-compressed form.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; checked against the Python non-zero count on 220 matrices.

C name

og_sparsemat_dropzeros

In notebooks

Og.Native.og_sparsemat_dropzeros

igraph 1.0

igraph_sparsemat_dropzeros

See also

sparsemat_droptol, sparsemat_fkeep, sparsemat_count_nonzero

Removes the elements whose magnitude is at most a tolerance.

og_error_t og_sparsemat_droptol(og_sparsemat_t *A, og_real_t tol);

Pieces are summed first; then every element with |x| <= tol is removed. NaN values are kept.

Parameters

• A The sparse matrix, in column-compressed form.
• tol The tolerance, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, or tol is negative or NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; checked against the Python count above the tolerance on 220 matrices.

C name

og_sparsemat_droptol

In notebooks

Og.Native.og_sparsemat_droptol

igraph 1.0

igraph_sparsemat_droptol

See also

sparsemat_dropzeros, sparsemat_count_nonzerotol

Multiplies every stored value by a constant.

og_error_t og_sparsemat_scale(og_sparsemat_t *A, og_real_t by);

Works on either layout. Scaling by 0 keeps the entries, now holding zeros (sparsemat_dropzeros removes them).

Parameters

• A The sparse matrix.
• by The factor.

Returns

OG_SUCCESS (the function cannot fail).

Complexity

O(nnz).

Checked

Unit tests.

C name

og_sparsemat_scale

In notebooks

Og.Native.og_sparsemat_scale

igraph 1.0

igraph_sparsemat_scale

See also

sparsemat_add

Reorders the rows and columns of a sparse matrix by two permutations.

og_error_t og_sparsemat_permute(
    const og_sparsemat_t *A,
    const og_vector_int_t *p,
    const og_vector_int_t *q,
    og_sparsemat_t *res
);

res(k, l) = A(p[k], q[l]): row k of the result is row p[k] of A, column l is column q[l]. p and q must be permutations of 0 .. nrow-1 and 0 .. ncol-1; NULL means the identity. The result is a new column-compressed matrix; rows inside a column are not sorted.

Parameters

• A The sparse matrix, in column-compressed form.
• p Row permutation, or NULL.
• q Column permutation, or NULL.
• res The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, or p or q has the wrong length or is not a permutation.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy on 220 matrices.

C name

og_sparsemat_permute

In notebooks

Og.Native.og_sparsemat_permute

igraph 1.0

igraph_sparsemat_permute

See also

sparsemat_index, sparsemat_transpose

Computes the transpose of a sparse matrix.

og_error_t og_sparsemat_transpose(
    const og_sparsemat_t *A,
    og_sparsemat_t *res
);

The result keeps the layout of A. A column-compressed matrix is transposed with a counting sort (Gustavson 1978), which also leaves the rows of every column in increasing order. A triplet matrix keeps its entry order with rows and columns exchanged.

Parameters

• A The sparse matrix.
• res The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; transposed twice and compared with numpy on 220 matrices.

C name

og_sparsemat_transpose

In notebooks

Og.Native.og_sparsemat_transpose

igraph 1.0

igraph_sparsemat_transpose

See also

sparsemat_sort, sparsemat_permute

Adds empty rows at the bottom of a sparse matrix.

og_error_t og_sparsemat_add_rows(og_sparsemat_t *A, og_int_t n);

Only the number of rows changes; no entry moves and nothing is allocated.

Parameters

• A The sparse matrix.
• n Number of rows to add, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL n is negative, or the row count would overflow.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_add_rows

In notebooks

Og.Native.og_sparsemat_add_rows

igraph 1.0

igraph_sparsemat_add_rows

See also

sparsemat_add_cols, sparsemat_resize

Adds empty columns at the right of a sparse matrix.

og_error_t og_sparsemat_add_cols(og_sparsemat_t *A, og_int_t n);

Existing entries do not move. A column-compressed matrix gets n more column starts.

Parameters

• A The sparse matrix.
• n Number of columns to add, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL n is negative, or the column count would overflow.
• OG_ENOMEM Not enough memory.

Complexity

O(1) for a triplet matrix, O(ncol + n) for a column-compressed one.

Checked

Unit tests.

C name

og_sparsemat_add_cols

In notebooks

Og.Native.og_sparsemat_add_cols

igraph 1.0

igraph_sparsemat_add_cols

See also

sparsemat_add_rows, sparsemat_resize

Replaces a sparse matrix by an empty one of a new shape.

og_error_t og_sparsemat_resize(
    og_sparsemat_t *A,
    og_int_t nrow,
    og_int_t ncol,
    og_int_t nzmax
);

The stored entries are dropped: the result is always an empty matrix in triplet form with room for nzmax entries, ready for sparsemat_entry, whatever the previous layout. On failure the matrix is unchanged.

Parameters

• A The sparse matrix.
• nrow New number of rows.
• ncol New number of columns.
• nzmax Room for entries.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A dimension or nzmax is negative.
• OG_ENOMEM Not enough memory.

Complexity

O(1) apart from the allocation.

Checked

Unit tests.

C name

og_sparsemat_resize

In notebooks

Og.Native.og_sparsemat_resize

igraph 1.0

igraph_sparsemat_resize

See also

sparsemat_init, sparsemat_add_rows, sparsemat_add_cols

Creates a copy of a sparse matrix with its entries ordered by column, then by row.

og_error_t og_sparsemat_sort(
    const og_sparsemat_t *A,
    og_sparsemat_t *sorted
);

The result keeps the layout of A. Pieces of one position are not summed; the sort is stable, so they keep their relative order. Done with counting sorts (two transposes for a column-compressed matrix).

Parameters

• A The sparse matrix.
• sorted The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

Exact: the order is checked against a Python reference on 220 matrices.

C name

og_sparsemat_sort

In notebooks

Og.Native.og_sparsemat_sort

igraph 1.0

igraph_sparsemat_sort

See also

sparsemat_getelements_sorted, sparsemat_transpose

Builds the column-compressed form of a triplet sparse matrix.

og_error_t og_sparsemat_compress(
    const og_sparsemat_t *A,
    og_sparsemat_t *res
);

The result is a new column-compressed matrix with the same entries, grouped by column with a counting sort. Inside each column the entries keep their triplet order, and pieces of one position stay separate (sparsemat_dupl sums them). A is not changed.

Parameters

• A The matrix, in triplet form.
• res The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not in triplet form.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz + ncol).

Checked

Exact: entry order and values checked on 220 matrices.

C name

og_sparsemat_compress

In notebooks

Og.Native.og_sparsemat_compress

igraph 1.0

igraph_sparsemat_compress

See also

sparsemat_dupl, sparsemat_init, sparsemat_entry

Sums the pieces stored for the same position of a column-compressed matrix.

og_error_t og_sparsemat_dupl(og_sparsemat_t *A);

Afterwards every position is stored at most once; the sum sits where its first piece was. Stored zeros, including sums that cancel, remain (sparsemat_dropzeros removes them). Done in place; the room is not changed. On failure the matrix is unchanged.

Parameters

• A The sparse matrix, in column-compressed form.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not in column-compressed form.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

Exact: checked on 220 matrices and in 300 operation chains against a dense model.

C name

og_sparsemat_dupl

In notebooks

Og.Native.og_sparsemat_dupl

igraph 1.0

igraph_sparsemat_dupl

See also

sparsemat_compress, sparsemat_dropzeros

Returns the number of rows of a sparse matrix.

og_int_t og_sparsemat_nrow(const og_sparsemat_t *A);

Reads the row count the matrix was made with (or last resized to). Entries are never consulted, so a matrix whose stored entries leave some rows empty still reports all of them.

Parameters

• A The sparse matrix.

Returns

The number of rows.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_nrow

In notebooks

Og.Native.og_sparsemat_nrow

igraph 1.0

igraph_sparsemat_nrow

See also

sparsemat_ncol

Returns the number of columns of a sparse matrix.

og_int_t og_sparsemat_ncol(const og_sparsemat_t *A);

Reads the column count the matrix was made with (or last resized to); empty columns count too.

Parameters

• A The sparse matrix.

Returns

The number of columns.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_ncol

In notebooks

Og.Native.og_sparsemat_ncol

igraph 1.0

igraph_sparsemat_ncol

See also

sparsemat_nrow

Tells which of the two layouts a sparse matrix uses.

og_sparsemat_type_t og_sparsemat_type(const og_sparsemat_t *A);

OG_SPARSEMAT_TRIPLET (0) or OG_SPARSEMAT_CC (1).

Parameters

• A The sparse matrix.

Returns

The layout.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_type

In notebooks

Og.Native.og_sparsemat_type

igraph 1.0

igraph_sparsemat_type

See also

sparsemat_is_triplet, sparsemat_is_cc, sparsemat_type_t

True when a sparse matrix uses the triplet layout.

og_bool_t og_sparsemat_is_triplet(const og_sparsemat_t *A);

A triplet matrix keeps each stored entry as its own (row, column, value) record, in the order the entries were added; duplicates are allowed and are added together when the matrix is compressed. Same as sparsemat_type(A) == OG_SPARSEMAT_TRIPLET.

Parameters

• A The sparse matrix.

Returns

true or false.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_is_triplet

In notebooks

Og.Native.og_sparsemat_is_triplet

igraph 1.0

igraph_sparsemat_is_triplet

See also

sparsemat_is_cc, sparsemat_compress

True when a sparse matrix uses the column-compressed layout.

og_bool_t og_sparsemat_is_cc(const og_sparsemat_t *A);

A column-compressed matrix keeps the entries column by column, with one start offset per column; it is what sparsemat_compress() makes and what the arithmetic, solvers and eigenvalue functions take. Same as sparsemat_type(A) == OG_SPARSEMAT_CC.

Parameters

• A The sparse matrix.

Returns

true or false.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_is_cc

In notebooks

Og.Native.og_sparsemat_is_cc

igraph 1.0

igraph_sparsemat_is_cc

See also

sparsemat_is_triplet, sparsemat_compress

Tells whether a sparse matrix is square and equal to its transpose.

og_error_t og_sparsemat_is_symmetric(
    const og_sparsemat_t *A,
    og_bool_t *result
);

Works on either layout. The test is exact and judges elements, not stored pieces: pieces of one position are summed and stored zeros are ignored, then the matrix is compared with its transpose. A non-square matrix gives false. A is not changed.

Parameters

• A The sparse matrix.
• result Receives true or false.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy (exact equality with the transpose) on 220 matrices, 36 of them symmetric.

C name

og_sparsemat_is_symmetric

In notebooks

Og.Native.og_sparsemat_is_symmetric

igraph 1.0

igraph_sparsemat_is_symmetric

See also

matrix_is_symmetric, sparsemat_transpose

Returns element (row, col) of a sparse matrix.

og_real_t og_sparsemat_get(
    const og_sparsemat_t *A,
    og_int_t row,
    og_int_t col
);

Works on either layout. All stored pieces at that position are summed; a position with nothing stored gives 0, and so does a position outside the matrix.

Parameters

• A The sparse matrix.
• row Row index.
• col Column index.

Returns

The element.

Complexity

O(entries of column col) for a column-compressed matrix, O(nnz) for a triplet one.

Checked

python-igraph exposes no sparse-matrix API; compared with numpy's dense form of the 220 fixture matrices.

C name

og_sparsemat_get

In notebooks

Og.Native.og_sparsemat_get

igraph 1.0

igraph_sparsemat_get

See also

sparsemat_index, sparsemat_as_matrix

Copies the stored entries of a sparse matrix into three vectors.

og_error_t og_sparsemat_getelements(
    const og_sparsemat_t *A,
    og_vector_int_t *i,
    og_vector_int_t *j,
    og_vector_t *x
);

Entries come in storage order, pieces and stored zeros included. i receives the row indices and x the values. For a triplet matrix j receives the column index of each entry; for a column-compressed matrix j receives the ncol + 1 column starts instead (column c holds entries j[c] .. j[c+1]-1). All three vectors must be initialised; they are resized.

Parameters

• A The sparse matrix.
• i Output row indices (initialised).
• j Output column indices or column starts (initialised).
• x Output values (initialised).

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + ncol).

Checked

Exact: the storage arrays are copied; unit tests in both layouts.

C name

og_sparsemat_getelements

In notebooks

Og.Native.og_sparsemat_getelements

igraph 1.0

igraph_sparsemat_getelements

See also

sparsemat_getelements_sorted, sparsemat_iterator_init

Copies the stored entries into three vectors, ordered by column and then by row.

og_error_t og_sparsemat_getelements_sorted(
    const og_sparsemat_t *A,
    og_vector_int_t *i,
    og_vector_int_t *j,
    og_vector_t *x
);

Like sparsemat_getelements, after sorting a copy of the matrix: entries are ordered by column, then by row. Pieces of one position are not summed; they stay next to each other in their original order. For a column-compressed matrix j receives the column starts.

Parameters

• A The sparse matrix.
• i Output row indices (initialised).
• j Output column indices or column starts (initialised).
• x Output values (initialised).

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python reference of the order on 220 matrices, both layouts.

C name

og_sparsemat_getelements_sorted

In notebooks

Og.Native.og_sparsemat_getelements_sorted

igraph 1.0

igraph_sparsemat_getelements_sorted

See also

sparsemat_getelements, sparsemat_sort

Returns the smallest stored element of a sparse matrix.

og_real_t og_sparsemat_min(og_sparsemat_t *A);

Only stored elements count: positions with nothing stored are not taken as zeros. For a column-compressed matrix the pieces of each position are first summed in place (hence the non-const argument); a triplet matrix is read as stored, piece by piece. If there is no memory for the summing, the pieces are read as stored too. NaN values are skipped. With nothing stored the result is +infinity.

Parameters

• A The sparse matrix.

Returns

The smallest stored element.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python reference over the summed stored values of 220 matrices.

C name

og_sparsemat_min

In notebooks

Og.Native.og_sparsemat_min

igraph 1.0

igraph_sparsemat_min

See also

sparsemat_max, sparsemat_minmax

Returns the largest stored element of a sparse matrix.

og_real_t og_sparsemat_max(og_sparsemat_t *A);

Only stored elements count: positions with nothing stored are not taken as zeros. For a column-compressed matrix the pieces of each position are first summed in place (hence the non-const argument); a triplet matrix is read as stored, piece by piece. If there is no memory for the summing, the pieces are read as stored too. NaN values are skipped. With nothing stored the result is -infinity.

Parameters

• A The sparse matrix.

Returns

The largest stored element.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python reference over the summed stored values of 220 matrices.

C name

og_sparsemat_max

In notebooks

Og.Native.og_sparsemat_max

igraph 1.0

igraph_sparsemat_max

See also

sparsemat_min, sparsemat_minmax

Returns the smallest and the largest stored element in one pass.

og_error_t og_sparsemat_minmax(
    og_sparsemat_t *A,
    og_real_t *min,
    og_real_t *max
);

Only stored elements count: positions with nothing stored are not taken as zeros. For a column-compressed matrix the pieces of each position are first summed in place (hence the non-const argument); a triplet matrix is read as stored, piece by piece. If there is no memory for the summing, the pieces are read as stored too. NaN values are skipped. With nothing stored, min is +infinity and max -infinity. Either output may be NULL.

Parameters

• A The sparse matrix.
• min Receives the minimum, or NULL.
• max Receives the maximum, or NULL.

Returns

OG_SUCCESS (the function cannot fail).

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python reference over the summed stored values of 220 matrices.

C name

og_sparsemat_minmax

In notebooks

Og.Native.og_sparsemat_minmax

igraph 1.0

igraph_sparsemat_minmax

See also

sparsemat_min, sparsemat_max

Counts the stored elements that are not zero.

og_int_t og_sparsemat_count_nonzero(og_sparsemat_t *A);

For a column-compressed matrix the pieces of each position are summed in place first, so two pieces 2 and -2 count as one zero; a triplet matrix is counted piece by piece. NaN counts as non-zero.

Parameters

• A The sparse matrix.

Returns

The number of non-zero stored elements.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python count on 220 matrices.

C name

og_sparsemat_count_nonzero

In notebooks

Og.Native.og_sparsemat_count_nonzero

igraph 1.0

igraph_sparsemat_count_nonzero

See also

sparsemat_count_nonzerotol, sparsemat_nonzero_storage, sparsemat_dropzeros

Counts the stored elements whose magnitude is above a tolerance.

og_int_t og_sparsemat_count_nonzerotol(og_sparsemat_t *A, og_real_t tol);

An element with |x| <= tol counts as zero, the same rule sparsemat_droptol uses to drop it. Pieces are summed first for a column-compressed matrix, as in sparsemat_count_nonzero. NaN counts.

Parameters

• A The sparse matrix.
• tol The tolerance.

Returns

The number of stored elements with |x| > tol.

Complexity

O(nnz + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with a Python count on 220 matrices with random tolerances.

C name

og_sparsemat_count_nonzerotol

In notebooks

Og.Native.og_sparsemat_count_nonzerotol

igraph 1.0

igraph_sparsemat_count_nonzerotol

See also

sparsemat_count_nonzero, sparsemat_droptol

Computes the sum of each row of a sparse matrix.

og_error_t og_sparsemat_rowsums(const og_sparsemat_t *A, og_vector_t *res);

Works on either layout; every stored piece is added to its row. res must be initialised and is resized to nrow.

Parameters

• A The sparse matrix.
• res Output vector (initialised); resized.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + nrow).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy row sums on 220 matrices, both layouts.

C name

og_sparsemat_rowsums

In notebooks

Og.Native.og_sparsemat_rowsums

igraph 1.0

igraph_sparsemat_rowsums

See also

sparsemat_colsums

Computes the sum of each column of a sparse matrix.

og_error_t og_sparsemat_colsums(const og_sparsemat_t *A, og_vector_t *res);

Works on either layout. res must be initialised and is resized to ncol.

Parameters

• A The sparse matrix.
• res Output vector (initialised); resized.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nnz + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy column sums on 220 matrices, both layouts.

C name

og_sparsemat_colsums

In notebooks

Og.Native.og_sparsemat_colsums

igraph 1.0

igraph_sparsemat_colsums

See also

sparsemat_rowsums

Counts the stored entries, pieces and explicit zeros included.

og_int_t og_sparsemat_nonzero_storage(const og_sparsemat_t *A);

Every stored piece counts, stored zeros included. This is the storage in use, not the number of non-zero elements (sparsemat_count_nonzero).

Parameters

• A The sparse matrix.

Returns

The number of stored entries.

Complexity

O(1).

Checked

Exact by construction; unit tests.

C name

og_sparsemat_nonzero_storage

In notebooks

Og.Native.og_sparsemat_nonzero_storage

igraph 1.0

igraph_sparsemat_nonzero_storage

See also

sparsemat_count_nonzero, sparsemat_realloc

Writes the non-zero entries of a sparse matrix to a stream as text.

og_error_t og_sparsemat_print(const og_sparsemat_t *A, FILE *outstream);

One line per non-zero stored entry, "(row, col) value" with the value in printf's %g format, in storage order. Stored zeros are skipped. For a column-compressed matrix a line "column j:" comes before the entries of each column that has a non-zero one, and the entry lines are indented. The format is Open Graph's own.

Parameters

• A The sparse matrix.
• outstream An open stream, for example stdout.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EFILE Writing to the stream failed.

Complexity

O(nnz + ncol).

Checked

Unit tests of the output text.

C name

og_sparsemat_print

In notebooks

Og.Native.og_sparsemat_print

igraph 1.0

igraph_sparsemat_print

See also

sparsemat_getelements, sparsemat_iterator_init

Computes the linear combination alpha A + beta B of two sparse matrices.

og_error_t og_sparsemat_add(
    const og_sparsemat_t *A,
    const og_sparsemat_t *B,
    og_real_t alpha,
    og_real_t beta,
    og_sparsemat_t *res
);

Both must be column-compressed and have the same shape. The result is a new column-compressed matrix with one entry per position (pieces summed). Positions where the sum is zero keep a stored zero; sparsemat_dropzeros removes them.

Parameters

• A First matrix, column-compressed.
• B Second matrix, column-compressed.
• alpha Factor of A.
• beta Factor of B.
• res The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A or B is not column-compressed, or their shapes differ.
• OG_ENOMEM Not enough memory.

Complexity

O(nnz(A) + nnz(B) + nrow + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy (alpha A + beta B) on 220 matrices.

C name

og_sparsemat_add

In notebooks

Og.Native.og_sparsemat_add

igraph 1.0

igraph_sparsemat_add

See also

sparsemat_multiply, sparsemat_scale

Computes the matrix product A B of two sparse matrices.

og_error_t og_sparsemat_multiply(
    const og_sparsemat_t *A,
    const og_sparsemat_t *B,
    og_sparsemat_t *res
);

Both must be column-compressed, with ncol(A) == nrow(B). The result is a new column-compressed matrix, built column by column with a scatter accumulator (Gustavson 1978); pieces are summed.

Parameters

• A Left factor, column-compressed.
• B Right factor, column-compressed.
• res The result; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A or B is not column-compressed, or ncol(A) != nrow(B).
• OG_EOVERFLOW The product would hold more entries than og_int_t can count.
• OG_ENOMEM Not enough memory.

Complexity

O(flops + nrow(A) + ncol(B)), flops being the multiply-adds: for every entry B(k, j), the entries of column k of A.

Checked

python-igraph exposes no sparse-matrix API; compared with numpy on 220 products.

C name

og_sparsemat_multiply

In notebooks

Og.Native.og_sparsemat_multiply

igraph 1.0

igraph_sparsemat_multiply

See also

sparsemat_gaxpy, sparsemat_add

Adds the product of a sparse matrix and a vector to a vector: res = res + A x.

og_error_t og_sparsemat_gaxpy(
    const og_sparsemat_t *A,
    const og_vector_t *x,
    og_vector_t *res
);

res must already hold the vector to add to, with nrow(A) elements (set it to zero for a plain product); x must have ncol(A) elements.

Parameters

• A The sparse matrix, in column-compressed form.
• x The vector multiplied, length ncol.
• res Input and output, length nrow.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, or x or res has the wrong length.

Complexity

O(nnz + ncol).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy (y + A x) on 220 matrices.

C name

og_sparsemat_gaxpy

In notebooks

Og.Native.og_sparsemat_gaxpy

igraph 1.0

igraph_sparsemat_gaxpy

See also

sparsemat_multiply

Starts an iterator over the stored entries of a sparse matrix.

og_error_t og_sparsemat_iterator_init(
    og_sparsemat_iterator_t *it,
    const og_sparsemat_t *sparsemat
);

The iterator walks the stored pieces in storage order (column by column for a column-compressed matrix, in insertion order for a triplet one) and starts at the first one. It keeps a pointer to the matrix, which must not change while the iterator is in use. Nothing is allocated, so there is nothing to destroy.

Parameters

• it The iterator to set up.
• sparsemat The matrix to walk.

Returns

OG_SUCCESS (the function cannot fail).

Complexity

O(ncol) at most (skips empty leading columns).

Checked

Unit tests in both layouts.

C name

og_sparsemat_iterator_init

In notebooks

Og.Native.og_sparsemat_iterator_init

igraph 1.0

igraph_sparsemat_iterator_init

See also

sparsemat_iterator_next, sparsemat_iterator_end, sparsemat_iterator_get

og_sparsemat_iterator_t it;
og_sparsemat_iterator_init(&it, &A);
while (!og_sparsemat_iterator_end(&it)) {
    og_int_t i = og_sparsemat_iterator_row(&it);
    og_int_t j = og_sparsemat_iterator_col(&it);
    og_real_t x = og_sparsemat_iterator_get(&it);
    printf("(%" OG_PRId ", %" OG_PRId ") %g\n", i, j, x);
    og_sparsemat_iterator_next(&it);
}

Moves an iterator back to the first stored entry.

og_error_t og_sparsemat_iterator_reset(og_sparsemat_iterator_t *it);

Puts the iterator on the first stored entry again, as sparsemat_iterator_init() left it: position 0 and, for a column-compressed matrix, the first column that holds an entry. Use it to walk the same matrix a second time.

Parameters

• it The iterator.

Returns

OG_SUCCESS (the function cannot fail).

Complexity

O(ncol) at most.

Checked

Unit tests.

C name

og_sparsemat_iterator_reset

In notebooks

Og.Native.og_sparsemat_iterator_reset

igraph 1.0

igraph_sparsemat_iterator_reset

See also

sparsemat_iterator_init

Tells whether an iterator has passed the last stored entry.

og_bool_t og_sparsemat_iterator_end(const og_sparsemat_iterator_t *it);

The iterator is past the end once its position reaches the number of stored entries; a matrix with no stored entries is at the end straight after sparsemat_iterator_init(). Check it before reading the current entry.

Parameters

• it The iterator.

Returns

true when there is no current entry.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_iterator_end

In notebooks

Og.Native.og_sparsemat_iterator_end

igraph 1.0

igraph_sparsemat_iterator_end

See also

sparsemat_iterator_next

Row index of the entry the iterator points at.

og_int_t og_sparsemat_iterator_row(const og_sparsemat_iterator_t *it);

Only valid while sparsemat_iterator_end is false.

Parameters

• it The iterator.

Returns

The row index.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_iterator_row

In notebooks

Og.Native.og_sparsemat_iterator_row

igraph 1.0

igraph_sparsemat_iterator_row

See also

sparsemat_iterator_col, sparsemat_iterator_get

Column index of the entry the iterator points at.

og_int_t og_sparsemat_iterator_col(const og_sparsemat_iterator_t *it);

Only valid while sparsemat_iterator_end is false.

Parameters

• it The iterator.

Returns

The column index.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_iterator_col

In notebooks

Og.Native.og_sparsemat_iterator_col

igraph 1.0

igraph_sparsemat_iterator_col

See also

sparsemat_iterator_row, sparsemat_iterator_get

Stored value of the entry the iterator points at.

og_real_t og_sparsemat_iterator_get(const og_sparsemat_iterator_t *it);

This is one stored piece; if the position has several pieces, each is visited separately. Only valid while sparsemat_iterator_end is false.

Parameters

• it The iterator.

Returns

The stored value.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_iterator_get

In notebooks

Og.Native.og_sparsemat_iterator_get

igraph 1.0

igraph_sparsemat_iterator_get

See also

sparsemat_iterator_row, sparsemat_iterator_col

Advances an iterator to the next stored entry.

og_int_t og_sparsemat_iterator_next(og_sparsemat_iterator_t *it);

For a column-compressed matrix, empty columns are skipped.

Parameters

• it The iterator.

Returns

The new position in the storage arrays (equal to the number of stored entries at the end).

Complexity

Amortised O(1); O(ncol + nnz) for a whole walk.

Checked

Unit tests.

C name

og_sparsemat_iterator_next

In notebooks

Og.Native.og_sparsemat_iterator_next

igraph 1.0

igraph_sparsemat_iterator_next

See also

sparsemat_iterator_end

Returns the position of the iterator's current entry in the storage arrays.

og_int_t og_sparsemat_iterator_idx(const og_sparsemat_iterator_t *it);

The index k such that the entry is row[k], val[k] of the matrix (and col[k] for a triplet matrix).

Parameters

• it The iterator.

Returns

The storage position.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_iterator_idx

In notebooks

Og.Native.og_sparsemat_iterator_idx

igraph 1.0

igraph_sparsemat_iterator_idx

See also

sparsemat_iterator_next

Prepares an LU decomposition: chooses the column order of a square sparse matrix.

og_error_t og_sparsemat_symblu(
    og_int_t order,
    const og_sparsemat_t *A,
    og_sparsemat_symbolic_t *dis
);

The symbolic step of sparsemat_lu. It only fixes the column order, so the result can be used for any matrix of the same shape, for example the same pattern with new values. order chooses the column order used to limit fill-in: 0 natural order, 1 approximate minimum degree (Amestoy, Davis and Duff 1996) of the pattern of A + A' (A square), 2 the same on A'A after leaving out dense rows of A (more than max(16, 10 sqrt(ncol)) entries), 3 the same on A'A.

dis must not be initialised; free it with sparsemat_symbolic_destroy. On failure it is left empty and safe to destroy.

Parameters

• order Column ordering, 0 to 3.
• A The square matrix, column-compressed.
• dis Receives the analysis; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed or not square, or order is not 0 to 3.
• OG_ENOMEM Not enough memory.

Complexity

O(1) for order 0; otherwise the minimum-degree ordering of the pattern (forming A'A for orders 2 and 3 costs the sum of the squared row counts of A).

Checked

No igraph comparison possible (no sparse API in python-igraph); every order is checked to be a permutation on thousands of structured patterns, and minimum-degree fill was within 0.98-1.13x of SuperLU's MMD order (scipy, black box) on 13 problems.

C name

og_sparsemat_symblu

In notebooks

Og.Native.og_sparsemat_symblu

igraph 1.0

igraph_sparsemat_symblu

See also

sparsemat_lu, sparsemat_symbqr, sparsemat_lusol, sparsemat_symbolic_destroy

Prepares a QR decomposition: column order, column elimination tree and row placement.

og_error_t og_sparsemat_symbqr(
    og_int_t order,
    const og_sparsemat_t *A,
    og_sparsemat_symbolic_t *dis
);

The symbolic step of sparsemat_qr. It chooses the column order (see below), builds the column elimination tree (the elimination tree of A'A, without forming A'A) and decides, by merging rows along that tree (George and Heath 1980; George, Liu and Ng 1988), which row of the factor every row of A becomes. A matrix with fewer rows than columns is analysed through its transpose, which sparsemat_qrresol uses to return the minimum-norm solution.

order chooses the column order used to limit fill-in: 0 natural order, 1 approximate minimum degree (Amestoy, Davis and Duff 1996) of the pattern of A + A' (A square), 2 the same on A'A after leaving out dense rows of A (more than max(16, 10 sqrt(ncol)) entries), 3 the same on A'A. dis must not be initialised; free it with sparsemat_symbolic_destroy.

Parameters

• order Column ordering, 0 to 3 (1 needs a square matrix).
• A The matrix, column-compressed; any shape.
• dis Receives the analysis; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, order is not 0 to 3, or order 1 with a non-square A.
• OG_ENOMEM Not enough memory.

Complexity

The ordering, plus O(nnz alpha(n)) for the tree and O(m log m) for the row merging.

Checked

No igraph comparison possible; checked through the solutions of sparsemat_qrresol (numpy lstsq) and on structured patterns (grids, stars, cliques, dense rows, tall and wide systems).

C name

og_sparsemat_symbqr

In notebooks

Og.Native.og_sparsemat_symbqr

igraph 1.0

igraph_sparsemat_symbqr

See also

sparsemat_qr, sparsemat_qrresol, sparsemat_symblu, sparsemat_symbolic_destroy

Solves L x = b for a lower triangular sparse matrix L.

og_error_t og_sparsemat_lsolve(
    const og_sparsemat_t *L,
    const og_vector_t *b,
    og_vector_t *res
);

Forward substitution, column by column. A must be column-compressed and square. The diagonal may sit anywhere in its column and may be stored in pieces. Triangularity is judged on elements: a stored zero (or pieces that cancel) on the wrong side of the diagonal is ignored. res is resized to n; res may be b itself.

Parameters

• L Lower triangular matrix, column-compressed.
• b Right-hand side, length n.
• res The solution (initialised); resized. May be b.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not column-compressed or not square, size(b) differs from n, the matrix has a non-zero element on the wrong side of the diagonal, or a zero on the diagonal.
• OG_ENOMEM Not enough memory.

Complexity

O(n + nnz(L)).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy.linalg.solve on 220 systems.

C name

og_sparsemat_lsolve

In notebooks

Og.Native.og_sparsemat_lsolve

igraph 1.0

igraph_sparsemat_lsolve

See also

sparsemat_ltsolve, sparsemat_usolve, sparsemat_utsolve

Solves L' x = b for a lower triangular sparse matrix L (using its transpose).

og_error_t og_sparsemat_ltsolve(
    const og_sparsemat_t *L,
    const og_vector_t *b,
    og_vector_t *res
);

Back substitution on the transpose, without forming it. A must be column-compressed and square. The diagonal may sit anywhere in its column and may be stored in pieces. Triangularity is judged on elements: a stored zero (or pieces that cancel) on the wrong side of the diagonal is ignored. res is resized to n; res may be b itself.

Parameters

• L Lower triangular matrix, column-compressed.
• b Right-hand side, length n.
• res The solution (initialised); resized. May be b.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not column-compressed or not square, size(b) differs from n, the matrix has a non-zero element on the wrong side of the diagonal, or a zero on the diagonal.
• OG_ENOMEM Not enough memory.

Complexity

O(n + nnz(L)).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy.linalg.solve on 220 systems.

C name

og_sparsemat_ltsolve

In notebooks

Og.Native.og_sparsemat_ltsolve

igraph 1.0

igraph_sparsemat_ltsolve

See also

sparsemat_lsolve, sparsemat_utsolve

Solves U x = b for an upper triangular sparse matrix U.

og_error_t og_sparsemat_usolve(
    const og_sparsemat_t *U,
    const og_vector_t *b,
    og_vector_t *res
);

Back substitution, column by column. A must be column-compressed and square. The diagonal may sit anywhere in its column and may be stored in pieces. Triangularity is judged on elements: a stored zero (or pieces that cancel) on the wrong side of the diagonal is ignored. res is resized to n; res may be b itself.

Parameters

• U Upper triangular matrix, column-compressed.
• b Right-hand side, length n.
• res The solution (initialised); resized. May be b.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not column-compressed or not square, size(b) differs from n, the matrix has a non-zero element on the wrong side of the diagonal, or a zero on the diagonal.
• OG_ENOMEM Not enough memory.

Complexity

O(n + nnz(U)).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy.linalg.solve on 220 systems.

C name

og_sparsemat_usolve

In notebooks

Og.Native.og_sparsemat_usolve

igraph 1.0

igraph_sparsemat_usolve

See also

sparsemat_utsolve, sparsemat_lsolve

Solves U' x = b for an upper triangular sparse matrix U (using its transpose).

og_error_t og_sparsemat_utsolve(
    const og_sparsemat_t *U,
    const og_vector_t *b,
    og_vector_t *res
);

Forward substitution on the transpose, without forming it. A must be column-compressed and square. The diagonal may sit anywhere in its column and may be stored in pieces. Triangularity is judged on elements: a stored zero (or pieces that cancel) on the wrong side of the diagonal is ignored. res is resized to n; res may be b itself.

Parameters

• U Upper triangular matrix, column-compressed.
• b Right-hand side, length n.
• res The solution (initialised); resized. May be b.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL The matrix is not column-compressed or not square, size(b) differs from n, the matrix has a non-zero element on the wrong side of the diagonal, or a zero on the diagonal.
• OG_ENOMEM Not enough memory.

Complexity

O(n + nnz(U)).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy.linalg.solve on 220 systems.

C name

og_sparsemat_utsolve

In notebooks

Og.Native.og_sparsemat_utsolve

igraph 1.0

igraph_sparsemat_utsolve

See also

sparsemat_usolve, sparsemat_ltsolve

Solves A x = b for a symmetric positive definite sparse matrix by Cholesky decomposition.

og_error_t og_sparsemat_cholsol(
    const og_sparsemat_t *A,
    const og_vector_t *b,
    og_vector_t *res,
    og_int_t order
);

Factors P A P' = L L' and solves with two triangular sweeps. Only the diagonal and the entries above it are read, so A may be stored whole or as its upper triangle. order 0 keeps the natural order; order 1 uses approximate minimum degree on the pattern of A + A'. The structure of L comes from the elimination tree (Liu 1990) before any arithmetic; the factor is computed column by column (George and Liu 1981).

A matrix that is not positive definite is reported when a pivot is not positive.

Parameters

• A The sparse matrix, in column-compressed form.
• b Right-hand side, length n.
• res The solution (initialised); resized.
• order 0 natural, 1 minimum degree.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed or not square, size(b) differs, or order is not 0 or 1.
• OG_FAILURE A is not positive definite.
• OG_EOVERFLOW The factor would hold more entries than og_int_t can count.
• OG_ENOMEM Not enough memory.

Complexity

The ordering plus O(n + nnz(L)) for the structure and the sum over columns of the squared column counts of L for the arithmetic.

Checked

python-igraph exposes no sparse-matrix API; compared with numpy on 220 symmetric positive definite systems, orders 0 and 1, plus residual checks on structured systems up to 3,600 unknowns.

C name

og_sparsemat_cholsol

In notebooks

Og.Native.og_sparsemat_cholsol

igraph 1.0

igraph_sparsemat_cholsol

See also

sparsemat_lusol, sparsemat_qrresol

Solves A x = b for a square sparse matrix by LU decomposition.

og_error_t og_sparsemat_lusol(
    const og_sparsemat_t *A,
    const og_vector_t *b,
    og_vector_t *res,
    og_int_t order,
    og_real_t tol
);

Runs sparsemat_symblu, sparsemat_lu and sparsemat_luresol and frees the factors. Use those three directly to solve several right-hand sides with one factorization. tol is the pivot threshold of sparsemat_lu: 1 gives partial pivoting by magnitude, smaller values prefer the diagonal.

Parameters

• A The sparse matrix, in column-compressed form.
• b Right-hand side, length n.
• res The solution (initialised); resized.
• order Column ordering, 0 to 3 (see sparsemat_symblu).
• tol Pivot threshold, usually in [0, 1].

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed or not square, size(b) differs, order is not 0 to 3, or tol is NaN.
• OG_FAILURE A is singular (no non-zero pivot at some step).
• OG_ENOMEM Not enough memory.

Complexity

As sparsemat_symblu plus sparsemat_lu plus O(n + nnz(L) + nnz(U)).

Checked

python-igraph exposes no sparse-matrix API; compared with numpy on 220 row-permuted systems that need pivoting (orders 0 to 3, tol 1, 0.1, 0.001), plus residual checks on structured and graph Laplacian matrices.

C name

og_sparsemat_lusol

In notebooks

Og.Native.og_sparsemat_lusol

igraph 1.0

igraph_sparsemat_lusol

See also

sparsemat_lu, sparsemat_luresol, sparsemat_cholsol, sparsemat_qrresol

/* A: n x n, column-compressed; b: length n */
og_vector_t x;
og_vector_init(&x, 0);
if (og_sparsemat_lusol(&A, &b, &x, 1, 1.0) == OG_SUCCESS) {
    /* x solves A x = b (minimum degree order, partial pivoting) */
}
og_vector_destroy(&x);

Computes the LU decomposition P A Q = L U of a square sparse matrix.

og_error_t og_sparsemat_lu(
    const og_sparsemat_t *A,
    const og_sparsemat_symbolic_t *dis,
    og_sparsemat_numeric_t *din,
    double tol
);

Q is the column order from sparsemat_symblu; P comes from pivoting. The factorization is left-looking and only touches the entries it needs (Gilbert and Peierls 1988). At each step the diagonal candidate is kept as pivot while |a_diag| >= tol * (largest candidate); otherwise the largest one is taken. tol 1 is partial pivoting; tol 0 keeps any non-zero diagonal, which can break down by cancellation on ill-conditioned matrices.

din receives L (multipliers below a unit diagonal), U (entries above its diagonal) and U's diagonal kept apart, plus the pivot step of every row. din must not be initialised; free it with sparsemat_numeric_destroy. On failure it is left safe to destroy.

Parameters

• A The sparse matrix, in column-compressed form.
• dis The analysis from sparsemat_symblu, for a matrix of A's shape.
• din Receives the factors; not initialised yet.
• tol Pivot threshold, usually in [0, 1].

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, dis is not an LU analysis or has another shape, or tol is NaN.
• OG_FAILURE A is singular (no non-zero pivot at some step).
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the floating-point work of the factorization, plus O(n + nnz(A)).

Checked

Checked by the backward error of P A Q = L U and the bound |L| <= 1/tol on 250 random matrices (orders 0 to 3, five tolerances), and through sparsemat_lusol against numpy.

C name

og_sparsemat_lu

In notebooks

Og.Native.og_sparsemat_lu

igraph 1.0

igraph_sparsemat_lu

See also

sparsemat_symblu, sparsemat_luresol, sparsemat_lusol, sparsemat_numeric_destroy

Computes the Householder QR decomposition of a sparse matrix.

og_error_t og_sparsemat_qr(
    const og_sparsemat_t *A,
    const og_sparsemat_symbolic_t *dis,
    og_sparsemat_numeric_t *din
);

With M = A (or A' when the analysis was made for a matrix with fewer rows than columns) and the column order from sparsemat_symbqr, the reflections bring M to the triangular factor R. din receives the reflection vectors (below an implicit unit entry), their coefficients, and R with its diagonal kept apart.

A column that is numerically in the span of the earlier ones gets an exact zero on R's diagonal (below 100 eps times the column's norm); sparsemat_qrresol then reports the rank deficiency. The analysis can be reused for another matrix of the same shape when its entries lie on the analysed tree paths; otherwise OG_EINVAL. din must not be initialised; free it with sparsemat_numeric_destroy.

Parameters

• A The sparse matrix, in column-compressed form.
• dis The analysis from sparsemat_symbqr.
• din Receives the factors; not initialised yet.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed, dis is not a QR analysis, or A does not fit the analysis (shape or pattern).
• OG_ENOMEM Not enough memory.

Complexity

Proportional to the floating-point work on R and the reflection vectors; dense rows of A make it costly.

Checked

Checked through sparsemat_qrresol against numpy lstsq, the normal equations and the minimum-norm solution, and on 2,981 reused analyses.

C name

og_sparsemat_qr

In notebooks

Og.Native.og_sparsemat_qr

igraph 1.0

igraph_sparsemat_qr

See also

sparsemat_symbqr, sparsemat_qrresol, sparsemat_numeric_destroy

Solves A x = b with an LU decomposition computed earlier.

og_error_t og_sparsemat_luresol(
    const og_sparsemat_symbolic_t *dis,
    const og_sparsemat_numeric_t *din,
    const og_vector_t *b,
    og_vector_t *res
);

Uses the analysis and the factors of sparsemat_symblu and sparsemat_lu; call it once per right-hand side.

Parameters

• dis The LU analysis.
• din The LU factors.
• b Right-hand side, length n.
• res The solution (initialised); resized.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL dis or din is not an LU result, they do not belong together, or size(b) differs from n.
• OG_ENOMEM Not enough memory.

Complexity

O(n + nnz(L) + nnz(U)).

Checked

python-igraph exposes no sparse-matrix API; several right-hand sides per factorization compared with numpy.

C name

og_sparsemat_luresol

In notebooks

Og.Native.og_sparsemat_luresol

igraph 1.0

igraph_sparsemat_luresol

See also

sparsemat_lu, sparsemat_lusol

Solves a linear system with a QR decomposition computed earlier: least squares or minimum norm.

og_error_t og_sparsemat_qrresol(
    const og_sparsemat_symbolic_t *dis,
    const og_sparsemat_numeric_t *din,
    const og_vector_t *b,
    og_vector_t *res
);

For A with at least as many rows as columns the result minimises ||A x - b|| (the exact solution of a consistent or square system). For A with fewer rows than columns it is the solution of A x = b with the smallest norm. b has nrow(A) elements and res is resized to ncol(A).

Parameters

• dis The QR analysis.
• din The QR factors.
• b Right-hand side, length nrow(A).
• res The solution (initialised); resized to ncol(A).

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL dis or din is not a QR result, they do not belong together, or size(b) differs.
• OG_FAILURE R has a zero on its diagonal: A is rank deficient and the solution is not unique.
• OG_ENOMEM Not enough memory.

Complexity

O(slots + nnz(V) + nnz(R)), V being the reflection vectors.

Checked

python-igraph exposes no sparse-matrix API; compared with numpy.linalg.lstsq (least squares and minimum norm) for all orders, and with the normal equations on 300 random systems.

C name

og_sparsemat_qrresol

In notebooks

Og.Native.og_sparsemat_qrresol

igraph 1.0

igraph_sparsemat_qrresol

See also

sparsemat_qr, sparsemat_symbqr, sparsemat_lusol

Frees the result of sparsemat_symblu or sparsemat_symbqr.

void og_sparsemat_symbolic_destroy(og_sparsemat_symbolic_t *dis);

Destroying twice, or a result whose creation failed, is harmless; NULL is ignored.

Parameters

• dis The analysis, or NULL.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_symbolic_destroy

In notebooks

Og.Native.og_sparsemat_symbolic_destroy

igraph 1.0

igraph_sparsemat_symbolic_destroy

See also

sparsemat_symblu, sparsemat_symbqr

Frees the result of sparsemat_lu or sparsemat_qr.

void og_sparsemat_numeric_destroy(og_sparsemat_numeric_t *din);

Destroying twice, or a result whose creation failed, is harmless; NULL is ignored.

Parameters

• din The factors, or NULL.

Returns

Nothing.

Complexity

O(1).

Checked

Unit tests.

C name

og_sparsemat_numeric_destroy

In notebooks

Og.Native.og_sparsemat_numeric_destroy

igraph 1.0

igraph_sparsemat_numeric_destroy

See also

sparsemat_lu, sparsemat_qr

Finds selected eigenpairs of a symmetric sparse matrix.

og_error_t og_sparsemat_arpack_rssolve(
    const og_sparsemat_t *A,
    og_arpack_options_t *options,
    og_arpack_storage_t *storage,
    og_vector_t *values,
    og_matrix_t *vectors,
    og_sparsemat_solve_t solvemethod
);

Runs the linalg area's arpack_rssolve (thick-restart Lanczos) with the sparse matrix as the operator. options->mode 1 iterates with A itself; mode 3 (shift and invert) iterates with (A - sigma I)^-1, which finds the eigenvalues nearest the shift options->sigma fast; any other mode is refused. options == NULL means mode 1, one eigenvalue, the one of largest magnitude. options->n is set to the size of A. In mode 3 the shifted matrix is factored once, by LU (minimum degree on A + A', partial pivoting) or by QR, as solvemethod says, and every iteration solves with that factorization.

values receives the nev eigenvalues in the order options->which asks for (LA, SA, LM, SM, BE); vectors the matching orthonormal eigenvectors as columns. storage may be NULL.

Parameters

• A Symmetric square matrix, column-compressed.
• options Solver options, or NULL for the defaults; n is set.
• storage Reusable work memory, or NULL.
• values Receives the eigenvalues (initialised).
• vectors Receives the eigenvectors as columns (initialised).
• solvemethod OG_SPARSEMAT_SOLVE_LU or OG_SPARSEMAT_SOLVE_QR: how mode 3 solves the shifted system.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed or not square, the mode is not 1 or 3, the solve method is unknown, or options are invalid (which, nev).
• OG_FAILURE Mode 3 with a shift that is an eigenvalue: the shifted matrix is singular.
• OG_EARPACK The iteration did not converge.
• OG_ENOMEM Not enough memory.

Complexity

Per iteration one product with A (O(nnz)) in mode 1, or one LU or QR solve in mode 3 after a single factorization; the number of iterations depends on the spectrum and options.

Checked

python-igraph exposes no sparse-matrix API; eigenvalues compared with numpy.linalg.eigvalsh on 40 random symmetric matrices (LA, SA, LM in mode 1; shift and invert by LU and QR in mode 3) and on 38 graph Laplacians + I, with eigenvector residuals.

C name

og_sparsemat_arpack_rssolve

In notebooks

Og.Native.og_sparsemat_arpack_rssolve

igraph 1.0

igraph_sparsemat_arpack_rssolve

See also

sparsemat_arpack_rnsolve, arpack_rssolve, arpack_options_init

/* largest eigenvalue of a symmetric column-compressed matrix A */
og_arpack_options_t opt;
og_vector_t values;
og_matrix_t vectors;
og_arpack_options_init(&opt);
opt.which[0] = 'L'; opt.which[1] = 'A';   /* largest algebraic */
opt.nev = 1;
og_vector_init(&values, 0);
og_matrix_init(&vectors, 0, 0);
og_sparsemat_arpack_rssolve(&A, &opt, NULL, &values, &vectors, OG_SPARSEMAT_SOLVE_LU);
/* VECTOR(values)[0] is the eigenvalue, column 0 of vectors its eigenvector */
og_matrix_destroy(&vectors);
og_vector_destroy(&values);

Finds selected eigenpairs of a general, non-symmetric sparse matrix.

og_error_t og_sparsemat_arpack_rnsolve(
    const og_sparsemat_t *A,
    og_arpack_options_t *options,
    og_arpack_storage_t *storage,
    og_matrix_t *values,
    og_matrix_t *vectors
);

Runs the linalg area's arpack_rnsolve (Krylov-Schur) with the sparse matrix as the operator. options->mode 1 iterates with A itself; mode 3 (shift and invert) iterates with (A - sigma I)^-1, which finds the eigenvalues nearest the shift options->sigma fast; any other mode is refused. options == NULL means mode 1, one eigenvalue, the one of largest magnitude. options->n is set to the size of A. Mode 3 takes a real shift only (options->sigmai must be 0) and factors the shifted matrix once by LU.

values receives one row per eigenvalue with the real and imaginary parts in two columns, ordered as options->which asks (LM, SM, LR, SR, LI, SI); a complex conjugate pair takes two adjacent rows, the one with the positive imaginary part first. vectors receives a column for each real eigenvalue and two columns (real and imaginary part) for each conjugate pair. storage may be NULL.

Parameters

• A Square matrix, column-compressed.
• options Solver options, or NULL for the defaults; n is set.
• storage Reusable work memory, or NULL.
• values Receives the eigenvalues, k x 2 (initialised).
• vectors Receives the eigenvectors (initialised).

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL A is not column-compressed or not square, the mode is not 1 or 3, sigmai is not 0 in mode 3, or options are invalid (which, nev).
• OG_FAILURE Mode 3 with a shift that is an eigenvalue: the shifted matrix is singular.
• OG_EARPACK The iteration did not converge.
• OG_ENOMEM Not enough memory.

Complexity

Per iteration one product with A (O(nnz)) in mode 1, or one LU solve in mode 3 after a single factorization.

Checked

python-igraph exposes no sparse-matrix API; eigenvalues compared with numpy.linalg.eigvals on 30 random non-symmetric matrices with complex pairs (LM, LR in mode 1; a real shift in mode 3) and on 47 directed graph Laplacians + I.

C name

og_sparsemat_arpack_rnsolve

In notebooks

Og.Native.og_sparsemat_arpack_rnsolve

igraph 1.0

igraph_sparsemat_arpack_rnsolve

See also

sparsemat_arpack_rssolve, arpack_rnsolve, arpack_unpack_complex

Converts a dense matrix into a sparse matrix, dropping elements close to zero.

og_error_t og_matrix_as_sparsemat(
    og_sparsemat_t *res,
    const og_matrix_t *mat,
    og_real_t tol
);

Every element with |x| <= tol is left out; the others are stored in triplet form, in column-major order. With tol = 0 exactly the non-zero elements are kept. NaN elements are kept. res must not be initialised.

Parameters

• res The sparse result; not initialised yet.
• mat The dense matrix.
• tol Tolerance, 0 or more.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_EINVAL tol is negative or NaN.
• OG_ENOMEM Not enough memory.

Complexity

O(nrow * ncol).

Checked

Unit tests.

C name

og_matrix_as_sparsemat

In notebooks

Og.Native.og_matrix_as_sparsemat

igraph 1.0

igraph_matrix_as_sparsemat

See also

sparsemat_as_matrix, sparsemat_compress

Expands a sparse matrix into an ordinary dense matrix_t.

og_error_t og_sparsemat_as_matrix(
    og_matrix_t *res,
    const og_sparsemat_t *spmat
);

Works on either layout; pieces of one position are summed, and positions with nothing stored become 0. res must be initialised; it is resized to nrow by ncol.

Parameters

• res The dense result (initialised); resized.
• spmat The sparse matrix.

Returns

OG_SUCCESS, or an error code.

Errors

• OG_ENOMEM Not enough memory.

Complexity

O(nrow * ncol + nnz).

Checked

python-igraph exposes no sparse-matrix API; it is the comparison path of every numpy fixture check.

C name

og_sparsemat_as_matrix

In notebooks

Og.Native.og_sparsemat_as_matrix

igraph 1.0

igraph_sparsemat_as_matrix

See also

matrix_as_sparsemat, sparsemat_get