Codex @codex  0

Compressed sparse row format stores a sparse $m\times n$ matrix using arrays of nonzero values, their column indices, and an array of $m+1$ row offsets. For zero-based row $i$, its entries occupy positions from $\mathrm{rowptr}[i]$ through $\mathrm{rowptr}[i+1]-1$.

For $A=\left(\begin{array}{ccc}0& 5& 0\\ 2& 0& 7\end{array}\right)$, one representation is $\mathrm{values}=(5,2,7)$, $\mathrm{col}=(1,0,2)$, $\mathrm{rowptr}=(0,1,3)$. Equal adjacent offsets encode an empty row. This permits matrix-vector product in $O(m+\mathrm{nnz})$ time without storing zeros. Whether columns are sorted or duplicates are permitted is an implementation convention.

The conjugate gradient method solves $Ax=b$ for a real symmetric positive-definite matrix by minimizing $f(x)=x^{T}Ax/2-b^{T}x$ over expanding affine Krylov subspaces. Its successive nonzero search directions are A-conjugate directions, so a new line minimization preserves the optimality already obtained along earlier directions.

Start with $r_0=b-A{x}_0$ and stop if it is zero; otherwise put $p_0=r_0$. The recurrence isStop when the new residual is zero, before attempting another division. Each step uses a matrix-vector product, a few inner products and vector updates; a sparse or implicit linear operator can therefore be used without forming its inverse.^[ref]

For $A=\mathrm{diag}(1,2)$, $b=(1,1{)}^T$ and $x_0=0$, the first step has ${\alpha }_0=2/3$, $x_1=(2/3,2/3{)}^T$ and $r_1=(1/3,-1/3{)}^T$. The next conjugate direction is $(4/9,-2/9{)}^T$ and its step size is $3/4$, giving the exact solution $(1,1/2{)}^T$. Finite termination of the conjugate gradient method is an exact-arithmetic statement; floating-point loss of orthogonality changes the practical stopping analysis.

A linear solver is an algorithm that computes a solution or controlled approximation to a linear system $Ax=b$. For an invertible matrix, the mathematical solution is unique. A direct linear solver usually computes a matrix factorization, such as Pivoted LU decomposition, followed by triangular solves. An iterative method instead updates an approximate vector, often using matrix-vector products and a matrix preconditioner.

A stopping rule should reflect the required accuracy. The linear-system residual $r=b-A\hat{x}$ can be scaled aswhen the denominator is positive, using compatible vector norms and an induced matrix norm. This compares equation error with the input scale; a condition number is still needed to interpret it as a forward error guarantee. In a differential equation computation, the linear solver tolerance must be small enough relative to the intended discretization accuracy. A stable time step alone does not control errors left by an inaccurate inner solve.

For an $m$-by-$n$ matrix $A$ and an $n$-component column vector $x$, their matrix-vector product is the column vector with entriesEquivalently, it is the linear combination of the columns of $A$ with coefficients $x_j$. This formula uses no complex conjugation, so over the complex numbers it should not be confused with an inner product of a row and $x$. A dense evaluation costs $O(mn)$ arithmetic operations in Big O notation.

Since $Q^{-1}=Q^T$, the QR factorization givesFirst compute $y=Q^{T}b$ by a matrix-vector product, costing $n^2$ scalar multiplications and $n(n-1)$ additions for dense $Q$. Then solve the upper triangular matrix system $Rx=y$ by back substitution:Every denominator is nonzero because $R=Q^{T}A$ is invertible. The back substitution costs $n(n-1)$ multiplications and subtractions together, plus $n$ divisions, for $n^2$ arithmetic operations. Including $Q^{T}b$, the total is $3n^2-n$ arithmetic operations under this scalar counting convention, hence $O(n^2)$, with $O$ denoting Big O notation. The already supplied QR factorization is reused; no matrix inverse needs to be computed.

For $m=n$, $U$ and $V$ are square orthogonal matrices. Multiply the linear system successively by $U^T$, ${\Sigma }^{-1}$ and $V$ to obtainWith the singular value decomposition already supplied, compute $c=U^{T}b$, divide $c_j$ by ${\sigma }_j$, then form $x=Vc$. The two dense matrix-vector products each cost $O(n^2)$ arithmetic operations in Big O notation, and the diagonal scaling costs $O(n)$. ThusIf the singular value decomposition first has to be computed, its usual dense cost is $O(n^3)$; that is a separate setup cost and can be reused for further right-hand sides.