Sparse matrix models and kernel costs

Let $F$ be a field, and let $m,n,s\in \mathbb{N}$, where $\mathbb{N}$ includes $0$. A compressed sparse row (CSR) record for an $m$ by $n$ matrix over $F$ consists of integer arrays $r=(r_0,\dots ,r_m)$ and $c=(c_0,\dots ,c_{s-1})$, and a value array $v=(v_0,\dots ,v_{s-1})\in F^s$, satisfying

$r_0=0,0=r_0\le r_1\le \cdots \le r_m=s,0\le c_t<n(0\le t<s)\mathrm{.}$

For each row $i<m$, its stored entries are the indices $t$ with $r_i\le t<r_{i+1}$. The row is empty exactly when $r_i=r_{i+1}$. Repeated column indices within one row and stored values $v_t=0_F$ are permitted; each such entry remains a separate stored entry.

The represented matrix $A\in M_{m\times n}(F)$ is defined entrywise by

$A_{ij}:={\sum }_{r_i\le t<r_{i+1}}{\mathbf{1}}_{c_t=j}{v}_t(0\le i<m,0\le j<n),$

where ${\mathbf{1}}_{c_t=j}$ is $1_F$ when $c_t=j$ and $0_F$ otherwise, and an empty sum is $0_F$. Repeated entries in column $j$ are therefore added. The number $s$ is the stored-entry count; it is not in general the number of nonzero entries of $A$.

A CSR record is canonical when no row repeats a column and no stored value is zero. In that case every nonzero matrix entry is stored exactly once and $s=\mathrm{nnz}(A)$, where $\mathrm{nnz}(A)$ denotes the number of nonzero entries of $A$. If $m=0$, the endpoint conditions force $s=0$ and the row-pointer array has its single entry $r_0=0$. If $n=0$, the column-index condition forces $s=0$ as well.

Let $F$ be a field, let $n\in \mathbb{N}$ (including $0$), and let $A\in M_{n\times n}(F)$ satisfy $A_{ij}=A_{ji}$ for every $i,j<n$ (that is, $A$ is symmetric). Its structural graph is the simple undirected graph $G_0=(V,E_0)$ with vertex set $V=\{0,\dots ,n-1\}$ and edge set

$E_0:=\{\{i,j\}:0\le i<j<n,A_{ij}\mathrm{\ne }0\}\mathrm{.}$

An elimination ordering is a listing $v_0,\dots ,v_{n-1}$ in which every vertex of $V$ occurs exactly once. Define the current vertex set by $V_k=\{v_{\mathrm{\ell }}:k\le \mathrm{\ell }<n\}$, starting with the structural graph $G_0$. At step $k$, the later neighbors of $v_k$ are

$N_k(v_k):=\{u\in V_k\setminus \{v_k\}:\{u,v_k\}\in E_k\}\mathrm{.}$

The filled graph $G_{k+1}=(V_{k+1},E_{k+1})$ is obtained by deleting $v_k$ and its incident edges, retaining all edges between remaining vertices, and adding every edge between two distinct vertices of $N_k(v_k)$. An edge added at step $k$ that was not already in $E_k$ is a fill edge. Repeating this rule defines the symbolic elimination pattern for the ordering; it is defined from the initial graph and ordering alone, without numerical pivot values.

If $N_k(v_k)$ is nonempty, the parent of $v_k$ is the later neighbor $v_{\mathrm{\ell }}$ with least position $\mathrm{\ell }>k$ in the ordering. If $N_k(v_k)$ is empty, $v_k$ is a root. Each non-root has a unique parent, and positions strictly increase along parent edges, so there is no directed cycle. If the underlying undirected graph had a cycle with $q$ vertices, orient its $q$ edges from child to parent. Each vertex has at most one outgoing parent edge, so these $q$ edges force every cycle vertex to have one outgoing edge along the cycle; following them gives a directed cycle, contradicting strict increase. Thus the parent relation is an elimination forest.

Fix a field $F$. The validated CSR matrix-vector product takes integer dimension candidates $m,n$, integer arrays $r,c$, a value array $v$ of elements of $F$, and a vector candidate $x$ of elements of $F$. All input arrays are finite; write $s=\mathrm{length}(v)$.

1. If $m\mathrm{\notin }\mathbb{N}$, $n\mathrm{\notin }\mathbb{N}$, $\mathrm{length}(r)\mathrm{\ne }m+1$, $\mathrm{length}(c)\mathrm{\ne }s$, or $\mathrm{length}(x)\mathrm{\ne }n$, return the status invalid-dimension.
2. For $i=0,\dots ,m$, check that $r_i\in \{0,\dots ,s\}$; return invalid-index if a check fails. Check $r_0=0$ and $r_m=s$, and for each $i=0,\dots ,m-1$ check $r_i\le r_{i+1}$; return invalid-index if any check fails. For each $t=0,\dots ,s-1$, check $0\le c_t<n$ and return invalid-index if a check fails.
3. Initialize $y_i=0_F$ for $0\le i<m$. For each row $i=0,\dots ,m-1$, and then each stored index $t=r_i,\dots ,r_{i+1}-1$, update $y_i\leftarrow y_i+v_t{x}_{c_t}\mathrm{.}$
4. Return the status ok together with $y\in F^m$.

For valid CSR data, each update uses exact field arithmetic. This procedure makes no floating-point rounding, backward-stability, convergence, runtime, or memory-bandwidth claim.

Let $F$ be a field, let $A\in M_{n\times n}(F)$ satisfy $A_{ij}=A_{ji}$ for all $i,j<n$, and fix an elimination ordering. Let $G_k=(V_k,E_k)$ be its symbolic filled graphs from Structural graphs and ordered symmetric elimination. Put $S^0=A$. Assume each pivot $p_k:=S_{v_k{v}_k}^k$ is nonzero, and for every pair of remaining vertices define the Schur update

$S_{ij}^{k+1}:=S_{ij}^k-\frac{S_{i{v}_k}^k{S}_{v_{k}j}^k}{p_k}\mathrm{.}$

Then for every stage $k$, each nonzero off-diagonal entry $S_{ij}^k$ has $\{i,j\}\in E_k$. At each elimination step, the later neighbors of the eliminated vertex form a clique in the next filled graph. Thus the symbolic filled graph contains each numerical Schur complement's off-diagonal support; equality of these off-diagonal patterns is not asserted.

The conclusion is a support inclusion, not equality: an arithmetic subtraction can cancel a nonzero entry while the symbolic edge remains. The companion page gives an explicit cancellation calculation in Numerical cancellation can zero an entry while the filled graph retains its edge ↗. No factorization-cost bound follows from this graph statement.

Let $F$ be a field, let $m,n\in \mathbb{Z}$, let $r,c$ be finite integer arrays, and let $v,x$ be finite arrays with entries in $F$. The algorithm Validated compressed sparse row matrix-vector product terminates on every such input. Its return status is invalid-dimension, invalid-index, or ok with a vector in $F^m$.

Let $F$ be a field, let $m,n\in \mathbb{N}$, let a valid CSR record represent $A\in M_{m\times n}(F)$, and let $x=(x_j{)}_{j<n}\in F^n$. Let $X\in M_{n\times 1}(F)$ be the column matrix with $X_{j0}=x_j$ for $j<n$, and define $Ax\in F^m$ by $(Ax{)}_i:=(AX{)}_{i0}={\sum }_{j<n}{A}_{ij}{x}_j(i<m),$ using Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes. Then the algorithm Validated compressed sparse row matrix-vector product returns ok with output $Ax$ in exact field arithmetic.

Let $F$ be a field, let $m,n\in \mathbb{N}$, and let a valid CSR record have $s$ stored entries. Its input arrays use exactly $s$ field-value slots, $s$ integer column-index slots, and $m+1$ integer row-pointer slots, for a total of $2s+m+1$ data slots. On valid input, the algorithm Validated compressed sparse row matrix-vector product performs exactly $s$ field multiplications, $s$ field additions, and $m$ zero initializations. Its index validation and loop-control work is $O(m+s+1)$. Counting the CSR arrays and returned output but excluding the supplied vector $x$ and constant-size workspace, it uses exactly $2s+2m+1$ data slots, hence $O(m+s+1)$ slots; for $m\ge 1$ this is $O(m+s)$. Here $O(g)$ means bounded by $Cg$ for a constant $C$ independent of the dimensions and input values.

For a square record of order $m\ge 1$ with at least one stored entry in each row, $s\ge m$, so the work and storage are $O(s)$. For a canonical record as defined in Compressed sparse row matrices with stored-entry semantics, $s=\mathrm{nnz}(A)$; without that convention, the cost is in terms of stored entries, not $\mathrm{nnz}(A)$. These are arithmetic, index, and storage counts, not runtime, memory-bandwidth, convergence, or factorization-cost bounds.