Numerical and Sparse Linear Algebra

Introduction

Linear algebra in artificial intelligence is rarely performed with exact real numbers or dense matrices. Computer arithmetic uses finite-precision floating-point representations, while modern datasets and models often contain millions or billions of parameters, most of which may be zero or effectively negligible. Numerical and sparse linear algebra provides the principles and algorithms needed to compute reliably and efficiently in this setting.

This chapter examines floating-point error, conditioning, numerical stability, computational complexity, direct and iterative linear-system solvers, power iteration, conjugate gradients, sparse matrix representations, and randomized matrix algorithms. These ideas are central to optimization, recommendation systems, graph learning, scientific machine learning, principal component analysis, simulation, and large-scale deep-learning systems.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish rounding error, truncation error, forward error, and backward error;
• explain conditioning and numerical stability;
• compare direct and iterative methods for solving linear systems;
• apply power iteration and conjugate gradients under their appropriate assumptions;
• select suitable sparse matrix representations;
• analyze time, memory, and communication complexity;
• explain how randomized algorithms accelerate large-scale matrix computation;
• evaluate numerical methods in an AI application.

1. Floating-Point Computation

1.1 Exact arithmetic versus machine arithmetic

A real number may have an arbitrarily long decimal or binary expansion, but a computer stores only a finite representation. In a simplified floating-point system, a nonzero number is represented as

\[

x = (-1)^s m b^e,

\]

where \(s\) is a sign bit, \(m\) is a significand, \(b\) is the numerical base, and \(e\) is an exponent. The stored value is generally a rounded approximation to the mathematical value.

For a standard floating-point format, the unit roundoff \(u\) is a measure of the maximum relative rounding error under normal conditions. With a common rounding-to-nearest model,

\[

\operatorname{fl}(x)=x(1+\delta), \qquad |\delta|\leq u,

\]

provided that overflow, underflow, and exceptional values do not occur. Here, \(\operatorname{fl}(x)\) denotes the machine representation of \(x\).

This model is useful but not universal. Subnormal numbers, overflow, underflow, cancellation, and hardware-specific fused operations can produce behavior that requires more careful analysis.

1.2 Sources of numerical error

Roundoff error is introduced when a real number or an arithmetic result is represented in finite precision. Truncation error occurs when an infinite process is replaced by a finite one, such as stopping an iterative method after a finite number of steps. Data error arises when input measurements or parameters are themselves inaccurate.

Two important measures are:

• Absolute error: \(|\hat{x}-x|\).
• Relative error: \(|\hat{x}-x|/|x|\), when \(x\neq 0\).

Here, \(x\) is the exact value and \(\hat{x}\) is the computed value. Relative error is often more informative when quantities vary greatly in scale.

A particularly dangerous phenomenon is catastrophic cancellation, in which two nearly equal numbers are subtracted. For example, if \(x\) and \(y\) are close, the absolute errors in their representations can be small while the relative error in \(x-y\) is very large. Algebraically equivalent formulas can therefore have very different numerical behavior.

1.3 Summation and accumulation

Adding many values can accumulate error. If positive and negative terms nearly cancel, the result may be especially inaccurate. More reliable approaches include pairwise summation, compensated summation, and ordering terms from small magnitude to large magnitude when appropriate. In parallel computing, pairwise reduction is often attractive because it improves both reproducibility and numerical behavior relative to an arbitrary sequential order.

2. Conditioning and Stability

2.1 Conditioning

Conditioning describes the sensitivity of a mathematical problem to perturbations in its input. It is a property of the problem, not primarily of the algorithm used to solve it.

For a differentiable scalar function \(f\), a local relative condition number is approximately

\[

\kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|,

\]

assuming \(x\neq 0\) and \(f(x)\neq 0\). A large value means that small relative input changes may cause large relative output changes.

For a nonsingular matrix \(A\), the condition number in a subordinate norm is

\[

\kappa(A)=\|A\|\,\|A^{-1}\|.

\]

In the Euclidean norm, \(\kappa_2(A)=\sigma_{\max}(A)/\sigma_{\min}(A)\), where \(\sigma_{\max}\) and \(\sigma_{\min}\) are the largest and smallest singular values. A matrix with a large condition number is called ill-conditioned. If \(A\) is singular, its condition number is infinite.

Conditioning places a limit on achievable accuracy. In a rough sense, if the input has relative error of order \(u\), the output may have relative error of order \(\kappa(A)u\), subject to problem-specific assumptions.

2.2 Stability

Stability describes the behavior of an algorithm. A backward-stable algorithm produces the exact answer for a nearby problem: it computes \(\hat{y}\) such that

\[

\hat{y}=f(x+\Delta x),

\]

where \(\Delta x\) is small relative to \(x\). A forward-stable algorithm produces a result close to the exact answer for the original input. Backward stability is often easier to establish and, for well-conditioned problems, implies useful forward accuracy.

A problem may be well-conditioned but solved by an unstable algorithm, or ill-conditioned but solved by a stable algorithm whose result is nevertheless sensitive to input error. This distinction is essential: conditioning concerns the task, whereas stability concerns the computational procedure.

2.3 Scaling and equilibration

Poorly scaled rows or columns can increase numerical difficulty and degrade iterative convergence. Scaling attempts to transform a system into an equivalent one with more balanced magnitudes. For example, diagonal matrices \(D_r\) and \(D_c\) may be chosen so that \(D_r A D_c\) has more comparable row and column norms. Scaling does not change the underlying solution when applied consistently, but it can improve numerical behavior.

3. Solving Linear Systems

A linear system has the form

\[

Ax=b,

\]

where \(A\in\mathbb{R}^{n\times n}\), \(x\in\mathbb{R}^n\), and \(b\in\mathbb{R}^n\). The objective is to compute \(x\), or an adequate approximation to it.

3.1 Gaussian elimination and LU factorization

For a general dense matrix, Gaussian elimination transforms \(A\) into an upper triangular matrix \(U\). With partial pivoting, row exchanges are performed to place a suitably large pivot in each elimination position. The resulting factorization is commonly written

\[

PA=LU,

\]

where \(P\) is a permutation matrix, \(L\) is lower triangular, and \(U\) is upper triangular.

After factorization, solve

\[

Ly=Pb, \qquad Ux=y,

\]

using forward and back substitution. For dense matrices, factorization requires approximately \(2n^3/3\) floating-point operations, while each triangular solve requires approximately \(O(n^2)\) operations. If many right-hand sides share the same matrix, factorization is reused, making LU particularly useful.

Pivoting improves robustness, although it can create additional nonzero entries, called fill-in, in sparse matrices.

3.2 Cholesky factorization

If \(A\) is symmetric positive definite (SPD), it has a factorization

\[

A=LL^T,

\]

where \(L\) is lower triangular with positive diagonal entries. Cholesky factorization requires roughly half the arithmetic of general LU and preserves symmetry. It is widely used in least squares, Gaussian-process models, covariance computations, and quadratic optimization.

The SPD conditions are important. A symmetric matrix that is not positive definite cannot safely be processed by ordinary Cholesky; an indefinite factorization such as an LDLᵀ method with pivoting may be required.

3.3 QR factorization and least squares

For an overdetermined system \(Ax\approx b\), the least-squares solution minimizes

\[

\|Ax-b\|_2^2.

\]

If \(A\) has full column rank, QR factorization writes \(A=QR\), where \(Q\) has orthonormal columns and \(R\) is upper triangular. The solution is obtained from

\[

Rx=Q^Tb.

\]

QR is generally more numerically reliable than forming the normal equations \(A^TAx=A^Tb\), because forming \(A^TA\) squares the 2-norm condition number: \(\kappa_2(A^TA)=\kappa_2(A)^2\) for full-rank \(A\).

4. Iterative Methods

Direct methods aim to obtain a solution after a finite sequence of algebraic operations, subject to roundoff. Iterative methods generate a sequence \(x_0,x_1,\ldots\) that ideally approaches the solution. They are often preferable when the matrix is very large, sparse, or accessed only through matrix-vector products.

4.1 Residuals and stopping criteria

For an approximate solution \(\hat{x}\), the residual is

\[

r=b-A\hat{x}.

\]

A small residual does not always imply a small solution error if \(A\) is ill-conditioned. A useful relative residual criterion is

\[

\frac{\|b-A\hat{x}\|}{\|b\|}\leq \tau,

\]

where \(\tau\) is a chosen tolerance and the norm is specified. Practical stopping rules may also monitor the change in iterates, a backward-error estimate, or a maximum iteration count.

4.2 Stationary iterations

For a splitting \(A=M-N\), the system can be written

\[

x=M^{-1}(Nx+b).

\]

This produces the iteration

\[

x^{(k+1)}=M^{-1}(Nx^{(k)}+b).

\]

Convergence depends on the spectral radius of the iteration matrix \(M^{-1}N\): convergence for every initial vector occurs when \(\rho(M^{-1}N)<1\). Jacobi and Gauss–Seidel methods are examples. They are conceptually important but may converge slowly or fail for difficult systems.

4.3 Power iteration

Power iteration estimates a dominant eigenvector. Given a nonzero initial vector \(x^{(0)}\), repeatedly compute

\[

y^{(k+1)}=Ax^{(k)},\qquad x^{(k+1)}=\frac{y^{(k+1)}}{\|y^{(k+1)}\|_2}.

\]

If \(A\) has an eigenvalue \(\lambda_1\) whose magnitude is strictly greater than all other eigenvalue magnitudes, and the initial vector has a nonzero component in its eigenvector direction, the normalized iterates converge to that dominant eigenvector up to sign. The asymptotic rate is governed approximately by \(|\lambda_2/\lambda_1|\). Thus, a small spectral gap causes slow convergence.

A Rayleigh quotient can estimate the eigenvalue:

\[

\mu_k=\frac{(x^{(k)})^T A x^{(k)}}{(x^{(k)})^T x^{(k)}}.

\]

For symmetric matrices, this estimate has particularly useful properties. Power iteration is important in ranking, spectral clustering, and principal-component computation, although more advanced methods are usually needed for several eigenvectors.

4.4 Conjugate gradients

The conjugate-gradient (CG) method solves

\[

Ax=b

\]

when \(A\) is symmetric positive definite. It minimizes the quadratic function

\[

f(x)=\frac{1}{2}x^TAx-b^Tx,

\]

whose unique minimizer is the solution of the system.

Starting with \(x_0\), set \(r_0=b-Ax_0\) and \(p_0=r_0\). At iteration \(k\), compute

\[

\alpha_k=\frac{r_k^Tr_k}{p_k^TAp_k},

\]

\[

x_{k+1}=x_k+\alpha_kp_k,

\]

\[

r_{k+1}=r_k-\alpha_kAp_k,

\]

and, for the standard formulation,

\[

\beta_k=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k},\qquad

p_{k+1}=r_{k+1}+\beta_kp_k.

\]

In exact arithmetic CG reaches the solution in at most \(n\) iterations, although practical convergence may occur much sooner. A standard bound for the energy-norm error is

\[

\|e_k\|_A\leq 2\left(\frac{\sqrt{\kappa(A)}-1}{\sqrt{\kappa(A)}+1}\right)^k\|e_0\|_A,

\]

where \(e_k=x_k-x_\), \(\|v\|_A=\sqrt{v^TAv}\), and \(x_\) is the exact solution. This is a bound rather than an exact prediction.

CG requires only matrix-vector products and vector operations. Its performance is strongly affected by the condition number and by memory access cost. Preconditioning replaces the original system by an equivalent one that is easier to solve. A preconditioner \(M\) should make \(M^{-1}A\) better conditioned while allowing efficient application of \(M^{-1}\). In practice, incomplete factorizations, diagonal scaling, and multigrid methods are common choices.

5. Sparse Linear Algebra

A matrix is sparse when most of its entries are zero. Sparsity should be understood relative to matrix size and computational purpose; there is no universal density threshold. Explicitly storing zeros wastes memory and computation.

5.1 Sparse formats

Coordinate (COO) format stores triples \((i,j,a_{ij})\). It is convenient for construction and conversion but may contain duplicate entries.

Compressed sparse row (CSR) stores nonzero values, their column indices, and row pointers. It supports efficient row traversal and sparse matrix-vector multiplication, making it common for iterative solvers.

Compressed sparse column (CSC) is the analogous column-oriented format and is convenient for column operations and some direct factorizations.

For a matrix with \(\operatorname{nnz}(A)\) nonzero entries, CSR storage is approximately proportional to \(\operatorname{nnz}(A)\) plus the number of rows, rather than \(n^2\). Sparse matrix-vector multiplication costs \(O(\operatorname{nnz}(A))\), compared with \(O(n^2)\) for a dense matrix.

Other formats include diagonal storage for banded matrices, block sparse row storage for dense subblocks, and specialized formats for symmetric or graph-based matrices. The best format depends on access patterns, hardware, and whether the sparsity pattern changes.

5.2 Sparse matrix-vector multiplication

For CSR, the product \(y=Ax\) is computed by traversing each row and accumulating products associated with its stored nonzeros. This operation is often the dominant cost in Krylov-subspace methods. Although its arithmetic count is low, performance may be limited by irregular memory access, index storage, load imbalance, and communication on parallel hardware.

5.3 Fill-in and ordering

Sparse direct factorization can produce fill-in: entries that were initially zero become nonzero in the factors. Fill-in increases memory and computation. Reordering rows and columns before factorization can reduce it. Common goals include reducing matrix bandwidth or approximating a minimum-degree elimination ordering. A method that is excellent for one sparsity pattern may be poor for another, so symbolic analysis is an important part of sparse computation.

6. Randomized Matrix Algorithms

Randomized algorithms use random samples or random projections to reduce computation while providing probabilistic accuracy guarantees. They are especially useful when matrices are too large for full decompositions.

A randomized range finder seeks a low-dimensional approximation to the column space of \(A\). Draw a random test matrix \(\Omega\in\mathbb{R}^{n\times (k+p)}\), where \(k\) is the target rank and \(p\) is an oversampling parameter, and form

\[

Y=A\Omega.

\]

An orthonormal basis \(Q\) for the columns of \(Y\) is then computed, usually with a numerically stable QR procedure. The matrix can be approximated by

\[

A\approx QQ^TA.

\]

The oversampling parameter helps capture directions that might otherwise be missed. Power iterations can improve the approximation when singular values decay slowly, using repeated applications of \(A\) and \(A^T\), with reorthogonalization as needed.

Randomized singular-value decomposition is useful in document analysis, image compression, recommendation, and feature extraction. Its advantages include fewer passes over data, suitability for parallel hardware, and scalability. Its limitations include probabilistic rather than deterministic error guarantees, sensitivity to numerical implementation, and the need to choose rank and oversampling intelligently.

7. Worked Example: Iterative Solution of an SPD System

Consider

\[

A=\begin{bmatrix}4&1\\1&3\end{bmatrix},\qquad

b=\begin{bmatrix}1\\2\end{bmatrix}.

\]

The matrix is symmetric. It is also positive definite because its leading principal minors are positive: \(4>0\) and \(4(3)-1(1)=11>0\). Therefore CG is applicable.

Choose \(x_0=(0,0)^T\). Then

\[

r_0=b-Ax_0=(1,2)^T,

\qquad p_0=r_0.

\]

Compute

\[

p_0^TAp_0=(1,2)\begin{bmatrix}4&1\\1&3\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix}

=(1,2)(6,7)^T=20.

\]

Thus

\[

\alpha_0=\frac{r_0^Tr_0}{p_0^TAp_0}=\frac{5}{20}=0.25,

\]

and

\[

x_1=x_0+0.25p_0=(0.25,0.5)^T.

\]

The new residual is

\[

r_1=r_0-0.25Ap_0=(1,2)^T-0.25(6,7)^T=(-0.5,0.25)^T.

\]

The exact solution, obtained independently, is

\[

x=A^{-1}b=\frac{1}{11}\begin{bmatrix}3&-1\\-1&4\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix}

=\begin{bmatrix}1/11\\7/11\end{bmatrix}.

\]

The first CG iterate is already closer to this solution than the initial vector. In exact arithmetic, the two-dimensional system is solved after at most two CG iterations. In larger problems, convergence depends substantially on eigenvalue clustering and preconditioning.

8. Applied Case: Sparse Recommendation-System Optimization

Background

Consider an illustrative online-learning company that recommends products to users. Its interaction matrix records clicks, ratings, and purchases. The matrix has millions of users and products, but each user interacts with only a small fraction of products, so it is highly sparse.

Problem

The company wants to estimate latent user and product factors by minimizing a regularized least-squares objective. Each training step requires operations involving sparse observations and, for some optimization variants, the solution of large linear systems. A dense implementation exceeds memory capacity and produces unacceptable latency.

Analysis

Storing the interaction matrix densely would require memory proportional to the product of the number of users and products, including mostly zero entries. CSR or COO storage reduces memory to a quantity proportional to the number of observed interactions. However, the matrix is not necessarily SPD, and ordinary CG cannot be applied directly to every formulation. The engineering team must distinguish between:

• normal-equation systems, which may be SPD but can square conditioning;
• QR- or LSQR-based approaches for least squares;
• preconditioned CG for genuinely SPD subproblems;
• stochastic or alternating optimization methods that avoid a global direct solve.

Approach and solution

The company stores observations in a construction-friendly COO format, then converts them to CSR for repeated row-based operations. It uses sparse matrix-vector products and parallel mini-batch updates. For an SPD regularized subproblem, preconditioned CG is selected, with diagonal or block-diagonal preconditioning. Residual-based stopping rules are combined with validation performance so that numerical convergence is not confused with recommendation quality.

The system also applies feature scaling and monitors the condition of small factor-update systems. Where a low-rank summary is useful for exploration, randomized range finding is used to obtain a compressed representation without computing a full singular-value decomposition.

Outcome

Memory use is reduced substantially because zero entries are not stored. Sparse kernels reduce arithmetic and permit larger datasets to fit in memory. Iterative methods avoid repeated cubic-cost factorization, while preconditioning reduces iteration counts. The team retains direct solvers for small subproblems, since sparse or iterative methods are not automatically superior at every scale.

Learning points

1. Sparsity is an algorithmic resource, not merely a storage property.

2. Solver choice must follow matrix structure: symmetry, definiteness, conditioning, and sparsity.

3. A small residual is not sufficient evidence of a useful model when the problem is ill-conditioned.

4. Numerical accuracy, runtime, memory, and predictive quality must be evaluated together.

9. Complexity, Implementation, and Professional Practice

Algorithm selection requires more than counting arithmetic operations. Important resources include memory capacity, memory bandwidth, parallel communication, synchronization, preprocessing, and numerical precision.

For dense matrices, storage is \(O(n^2)\), matrix-vector multiplication is \(O(n^2)\), and factorization is typically \(O(n^3)\). For sparse matrices, storage and multiplication are often expressed in terms of \(\operatorname{nnz}(A)\), but irregular access may prevent ideal hardware utilization. A method with fewer floating-point operations can be slower if it requires more data movement.

Best practices include:

• inspect symmetry, definiteness, rank, scale, and sparsity before choosing an algorithm;
• avoid explicitly forming matrix inverses when solving systems;
• use pivoting or structure-appropriate factorizations;
• use QR or SVD when least-squares conditioning is important;
• monitor residuals and, when possible, backward error;
• choose tolerances relative to data scale and application requirements;
• use preconditioning for large iterative systems;
• validate results with independent checks or alternative formulations;
• record precision, software versions, tolerances, random seeds, and stopping criteria for reproducibility.

In AI systems, numerical failures can become governance and safety issues. An unstable solver may produce biased rankings, invalid risk scores, or unreliable medical predictions. Reproducibility is also important when randomized algorithms influence decisions. Practitioners should document uncertainty, test sensitivity to perturbations, protect data used in randomized sketches, and avoid treating numerical output as more certain than the underlying data justify.

10. Challenges and Limitations

No numerical method is universally best. Direct methods can be robust but may suffer from fill-in and high memory requirements. Iterative methods can scale well but may stagnate, require preconditioners, or be sensitive to stopping rules. CG is restricted to SPD systems; applying it to an indefinite or nonsymmetric matrix violates its assumptions. Power iteration may converge slowly when the spectral gap is small and may fail to identify the desired eigenvector when initialization is unsuitable. Randomized methods provide scalable approximations but introduce probabilistic error and implementation complexity.

Finite precision can also destroy theoretical properties such as exact orthogonality or conjugacy. Consequently, practical implementations may require reorthogonalization, residual replacement, stable factorizations, or higher precision. Numerical methods should therefore be treated as engineered components whose behavior must be tested on representative data.

Chapter Summary

Numerical linear algebra studies how finite-precision computation affects the solution of mathematical problems. Floating-point arithmetic introduces roundoff, while cancellation, scaling, and ill-conditioning can amplify error. Conditioning is a property of a problem; stability is a property of an algorithm. Gaussian elimination with pivoting, Cholesky, and QR are important direct methods, while stationary iterations, power iteration, and conjugate gradients provide scalable iterative alternatives. CG is especially effective for large symmetric positive-definite systems and benefits from preconditioning. Sparse formats such as COO, CSR, and CSC reduce memory and computational costs, although fill-in and irregular memory access remain important limitations. Randomized range finding and low-rank methods accelerate large matrix approximations by using random projections. In professional AI practice, solver selection must consider structure, accuracy, conditioning, memory, hardware, reproducibility, and the consequences of numerical failure.

Key Terms

Floating-point arithmetic: Finite-precision representation and computation of numerical values.

Unit roundoff: A bound measuring the scale of rounding error in a floating-point system.

Roundoff error: Error introduced by finite-precision representation or arithmetic.

Truncation error: Error caused by replacing an infinite process with a finite approximation.

Catastrophic cancellation: Severe loss of relative accuracy when nearly equal quantities are subtracted.

Condition number: A measure of a problem’s sensitivity to input perturbations.

Numerical stability: The tendency of an algorithm to control the effects of computational error.

Backward stability: The property that a computed result is exact for a nearby input problem.

Residual: The vector \(b-A\hat{x}\) associated with an approximate solution.

LU factorization: Decomposition of a suitably permuted matrix into lower and upper triangular factors.

Cholesky factorization: The factorization \(A=LL^T\) for a symmetric positive-definite matrix.

QR factorization: Decomposition into an orthonormal factor and an upper triangular factor.

Iterative method: An algorithm that generates successive approximations to a solution.

Power iteration: An iterative method for estimating a dominant eigenvector.

Conjugate gradients: An iterative solver for symmetric positive-definite systems.

Preconditioner: An efficiently applied transformation intended to improve iterative convergence.

Sparsity: A matrix property in which most entries are zero.

Fill-in: New nonzero entries created during sparse factorization.

Randomized range finder: A random-projection method for approximating a matrix’s column space.

Spectral gap: The separation between a dominant eigenvalue magnitude and the next competing magnitude.

Review Questions

Short Answer Questions

1. Distinguish conditioning from numerical stability.

2. What is catastrophic cancellation, and why is it harmful?

3. State the structural requirements for applying the conjugate-gradient method.

4. Why is CSR format useful for sparse matrix-vector multiplication?

5. What does a preconditioner attempt to achieve?

Long Answer Questions

1. Explain floating-point error, relative error, backward error, and the effects of scaling.

2. Compare LU, Cholesky, and QR factorization, including their assumptions and applications.

3. Derive the main steps of power iteration and discuss its convergence conditions.

4. Explain conjugate gradients, its quadratic interpretation, convergence behavior, and limitations.

5. Compare direct, iterative, sparse, and randomized approaches for large AI datasets.

Analytical / Application Questions

1. A matrix is symmetric but indefinite. Which common solver from this chapter should not be applied without modification, and what alternatives could be considered?

2. An iterative solver reports a small residual, but the estimated solution changes greatly after a small perturbation to the data. Explain this observation using conditioning.

3. Design a numerical strategy for a recommendation system with a highly sparse interaction matrix. Justify the storage format, solver choices, stopping criteria, and validation procedures.

Multiple Choice Questions with Answers

Question 1

Which statement correctly distinguishes conditioning from stability?

A. Conditioning concerns the problem, while stability concerns the algorithm.

B. Conditioning concerns only sparse matrices, while stability concerns only dense matrices.

C. Conditioning is always improved by using more iterations.

D. Stability measures the number of nonzero matrix entries.

Correct Answer: A. Conditioning concerns the problem, while stability concerns the algorithm.

Question 2

For a full-column-rank matrix A, what is the main numerical disadvantage of forming the normal equations?

A. They eliminate the need for a solver.

B. They square the 2-norm condition number.

C. They always produce a nonsymmetric system.

D. They require A to be square.

Correct Answer: B. They square the 2-norm condition number.

Question 3

Which factorization is specifically appropriate for a symmetric positive-definite matrix?

A. Cholesky factorization

B. Unpivoted QR only

C. Singular diagonal factorization

D. COO factorization

Correct Answer: A. Cholesky factorization

Question 4

What is the computational cost of sparse matrix-vector multiplication in terms of the number of nonzeros?

A. O(n^3)

B. O(n^2) regardless of sparsity

C. O(nnz(A))

D. O(log n)

Correct Answer: C. O(nnz(A))

Question 5

Power iteration converges most rapidly when:

A. All eigenvalues have equal magnitude

B. The dominant eigenvalue has a large spectral gap

C. The matrix contains no eigenvectors

D. The initial vector is exactly zero

Correct Answer: B. The dominant eigenvalue has a large spectral gap

Question 6

Which condition is required by the standard conjugate-gradient method?

A. A must be rectangular and random

B. A must be symmetric positive definite

C. A must contain no zero entries

D. A must be diagonal

Correct Answer: B. A must be symmetric positive definite

Question 7

What is fill-in in sparse factorization?

A. Removal of all nonzero entries

B. New nonzero entries created in the factors

C. Random noise added to the right-hand side

D. A method for estimating eigenvalues

Correct Answer: B. New nonzero entries created in the factors

Question 8

In a randomized range finder, what is the primary role of the random matrix Ω?

A. To test and sample the column space of A

B. To replace the input matrix with zeros

C. To guarantee an exact inverse

D. To enforce symmetry in every matrix

Correct Answer: A. To test and sample the column space of A

Question 9

For the system in the worked example, what is the exact solution?

A. (1/11, 7/11)^T

B. (7/11, 1/11)^T

C. (1/4, 1/2)^T

D. (1/3, 2/3)^T

Correct Answer: A. (1/11, 7/11)^T

Question 10

Why can a small residual fail to guarantee a small solution error?

A. Residuals are defined only for sparse matrices.

B. An ill-conditioned matrix can amplify perturbations and residual-related errors.

C. A residual is always larger than the solution.

D. Residuals do not depend on the computed solution.

Correct Answer: B. An ill-conditioned matrix can amplify perturbations and residual-related errors.