Expand description
§Chapter 12.0.5 — Linear operators
§Purpose
The randomized and Krylov drivers (crate::rsvd(), crate::svds(),
later eigs/eigsh) never look inside the matrix: they only ask for
y ← A x and y ← Aᵀ x. LinearOperator and AdjointOperator are
that interface (decision S5 of D-0127): &mut self because useful
operators keep state (a counter, a workspace, a factorization whose solve
needs &mut), fallible because a user’s inner solve can fail and the
crate promises errors, not panics.
§Notation
A ∈ T^{m×n} (m = nrows(), n = ncols()); x, y vectors; X ∈ T^{n×l}, Y ∈ T^{m×l} blocks (column-major views, Chapter 12.0.2).
y is always overwritten, never accumulated.
§Algorithm A (the implementations of this crate)
A1. [Check.] |x| = n, |y| = m (for Aᵀ: |x| = m, |y| = n);
otherwise an OperatorError (the drivers never trigger it; a direct
caller may).
A2. [Dense, A x.] y ← 0; for k = 0, …, n − 1: y ← y + a_k x_k
(column-oriented gaxpy, a_k the k-th column).
A3. [Dense, Aᵀ x.] y_j ← a_jᵀ x, the dot product in index order.
A4. [CSC.] A x as A2 over the stored entries (skipping x_k = 0, as
CscMatrix::gaxpy); Aᵀ x as A3 over the stored entries of each
column.
A5. [CSR.] A x: a dot product per row over its stored entries; Aᵀ x: y ← 0, then for every row i in order, y_j ← y_j + a_ij x_i
(scatter).
A6. [Blocks.] Y ← A X column by column. The dense implementations
override the default with the same operations in the same order,
so apply_block and a loop of apply give the same bits
(determinism R2 does not depend on which one a driver calls).
A sparse matrix whose public fields were made inconsistent (an index out
of range) gives an OperatorError, not a panic: every index is read
with a checked access.
§Invariants
(O1) apply writes every entry of y (no stale values survive).
(O2) For the implementations here, apply_block equals, bit for bit, the
loop of apply over the columns (tested).
§References
Lehoucq, Sorensen & Yang, ARPACK Users’ Guide (1998), reverse
communication (the interface this trait replaces); faer 0.24.4
matrix_free::LinOp (read, not copied). Cited from memory.
Structs§
- FnAdjoint
Operator - An operator and its transpose from two closures. Build with
from_fns. - FnOperator
- An operator from a closure
f(x, y)writingy ← A x(PLAN L3.1’s “operador-closure”). Build withfrom_fn. - Operator
Error - An error reported by a
LinearOperator(for instance a closure whose inner solve failed). Carries a message only, so thatcrate::StatlaErrorstaysClone + PartialEq.
Constants§
Traits§
- Adjoint
Operator - An operator that also applies its transpose:
y ← Aᵀ x. Needed bycrate::rsvd()andcrate::svds(). - Linear
Operator y ← A xfor annrows × ncolsoperator known only by its action.
Functions§
- block_
parts 🔒 - The storage of a block, or an error if its public fields disagree.
- check 🔒
- Step A1: the length check of an application.
- check_
block 🔒 - The shape check of a block application (step A1 for blocks).
- dense_
apply 🔒 - Step A2 on a column-major
rows × colsarray with leading dimensionld. - dense_
apply_ 🔒t - Step A3.
- dense_
block 🔒 - Step A6 for dense storage: the columns of the block, each by A2 or A3.
- from_fn
FnOperatorof the closuref.- from_
fns FnAdjointOperatoroff(y ← A x) andg(y ← Aᵀ x).- gather 🔒
Σ a_i x_iover stored entries (A3 on a sparse column), checked.- scatter 🔒
y ← y + a x_kover stored entries (A2 on a sparse column), checked.- segment 🔒
- The stored entries
ptr[j]..ptr[j+1]of a compressed matrix, checked.