Question bank — scipy.sparse — sparse matrix formats (CSR, CSC), sparse solvers

False. Each nonzero costs one value plus one integer index (the indices entry), i.e. $\approx 1$ extra int per nonzero, so once density climbs past the crossover ($\rho \approx 1/2$ for equal-width value/index types, per the cost model above) the index overhead can make the sparse copy larger than the plain dense array.

True. Both use data, indices, indptr; CSR reads row-by-row with indices = column numbers, CSC reads column-by-column with indices = row numbers. It is one idea applied along the other axis.

True. indptr holds one start-offset per row plus a final sentinel equal to nnz; its length depends only on the number of rows (or columns for CSC), never on how many nonzeros exist.

True (usefully). COO allows duplicate (i,j) triples; conversion sums duplicates into a single entry, so several COO triples can collapse to one CSR nonzero, lowering nnz.

Mostly true in exact arithmetic, but how differs: spsolve factors (direct, one exact solve) while CG iterates toward the answer and stops at a tolerance, so its result is only approximate to that tolerance.

True. A tridiagonal $n\times n$ matrix has $\approx 3n$ nonzeros but $n^2$ dense slots; for large $n$ that is a huge waste, which is exactly why 1D PDE discretizations are stored sparse.

For the legacy spmatrix classes * historically meant matrix-multiply, which broke NumPy's elementwise convention; for the newer sparray arrays (SciPy $\ge 1.8$) * is elementwise and @ is the only guaranteed matrix-multiply. Because the meaning of * flips between the two class families, always write @ for matmul and .multiply() for elementwise.

False. Krylov methods such as CG only need the action $x\mapsto Ax$ (an SpMV) — never an explicit factorization — which is precisely why they dodge fill-in and stay low-memory.

Wrong: CSR keeps each row's nonzeros in one contiguous slice of data/indices, so inserting a new nonzero means opening a gap — every entry after position $(i,j)$ must shift up by one and every later indptr offset must increase by one, an $O(\text{nnz})$ rewrite that also triggers SparseEfficiencyWarning. Build in COO/LIL/DOK (which allow cheap insertion), then .tocsr() once.

Not a bug: CG's update directions are only guaranteed to reduce the error when $A$ is SPD, because the algorithm minimizes the energy $\frac{1}{2}{x}^{\top }Ax-b^{\top }x$, which needs $A$ positive-definite to have a minimum. On a non-symmetric or indefinite matrix that quadratic has no minimum, so it can stagnate or diverge; use gmres or bicgstab for the general case.

It works but silently transposes/converts to CSC first because sparse LU eliminates variables column-by-column and therefore needs $O(1)$ column access; that hidden conversion copies the whole matrix, so passing CSC directly saves both the copy time and the extra memory.

At $\rho =0.4$ you are far from sparse territory: with $\approx 2\text{nnz}$ numbers stored plus index-driven indirect memory access (each column lookup jumps around $x$), sparse is usually slower than a contiguous dense ndarray. Sparse pays off only when $\rho$ is genuinely small (the practical rule $\rho \lesssim 0.1$, well below the storage break-even).

Wrong cost model: a dense product touches all $n^2$ entries, but CSR loops only over the stored nonzeros, and each nonzero $A_{ij}$ contributes exactly one multiply-add $A_{ij}{x}_j$ to $y_i$ — so the total work is one operation per nonzero, giving $O(\text{nnz})$.

Each append into CSR is the expensive $O(\text{nnz})$ data-shift described above, so building $E$ edges costs $O(E^2)$; instead accumulate edges as COO triples ($O(1)$ per append, duplicates auto-summed for multi-edges) and pay a single sort-and-compress at .tocsr().

Symmetry alone is insufficient: Cholesky computes $A=L{L}^{\top }$, and the diagonal of $L$ involves square roots of pivots that are only guaranteed positive when $A$ is positive-definite. A symmetric-but-indefinite matrix hits a non-positive pivot, so no real Cholesky factor exists and the routine fails.

Because within a row the row-number is constant, so COO's row array is redundant; indptr stores only where each row starts (length $n+1$), compressing that repetition — the "Compressed" in CSR.

LU and Cholesky factorizations eliminate variables column-by-column, so column access must be fast; CSC gives $O(1)$ column slices, whereas CSR would need a costly transpose.

Krylov convergence depends on the matrix's conditioning; a preconditioner $M\approx A$ (cheap to invert) transforms the system so the solver converges in far fewer SpMVs.

SpMV sums each row's nonzeros against $x$; CSR already groups nonzeros by row and stores them contiguously, so the loop is cache-friendly and touches each nonzero exactly once.

Direct factorization can turn many stored zeros into nonzeros, blowing up memory to well beyond the original nnz; iterative solvers never factorize, so they sidestep fill-in entirely — a key trade-off.

COO insertion is $O(1)$ per triple with duplicates summed later, while CSR insertion is $O(\text{nnz})$ per new entry; you pay the sort/compress cost once at conversion instead of on every insert.

data and indices are empty, and indptr is all zeros of length $n+1$ — every row's start equals its end, so every slice is empty. Valid and consistent.

CSR stores $n$ nonzeros plus an $(n+1)$-length indptr ($\approx 3n$ numbers) versus $n^2$ dense — a large win, and its density $\rho =1/n\to 0$ as $n$ grows.

They are summed, so (i,j, +5) and (i,j, -5) collapse to a stored 0; unless explicitly pruned this can leave an explicit zero — a stored entry whose value is zero — inflating nnz.

No exact solution exists when $A$ is singular; the factorization hits a zero pivot and either errors or returns garbage/nan. Detect near-singularity via conditioning, not by trusting the output.

Yes — the format is dimension-agnostic: a $0\times 0$ matrix has indptr = [0] (length $n+1=1$) and empty data/indices, so no special-casing is needed at the boundary.

Near $\rho \approx 1/2$ when a value and an index occupy equal bytes (each nonzero then costs $2\times$ a dense slot), shifting toward $\rho \approx 2/3$ when indices are half-width (int32 vs float64); below that sparse saves bytes, above it dense wins. The stricter practical rule $\rho \lesssim 0.1$ also targets speed, not just storage.

Yes — for an $n\times m$ matrix, CSR's indptr has length $n+1$ (rows) and CSC's has length $m+1$ (columns); such rectangular systems arise in least-squares solvers like lsqr/lsmr.