A direct analytical method that expresses the solution in terms of determinants. While conceptually simple, Cramer's rule is computationally impractical for systems larger than $3 \times 3$ due to the factorial growth in computing determinants ($O(n!)$ operations).

To compare algorithms, we count the floating-point operations (FLOPs), primarily multiplications and divisions.

• Forward Elimination: Requires approximately $\frac{2n^3}{3}$ FLOPs.
• Back Substitution: Requires approximately $n^2$ FLOPs.
• Total: Thus, Gauss Elimination is an $O(n^3)$ operation, specifically dominated by the $n^3/3$ multiplications. This cubic scaling means doubling the size of a system multiplies the execution time by eight.

• Partial Pivoting: The most common approach. Before eliminating variables in column $k$, it searches the remaining rows $i \ge k$ for the largest absolute element $|a_{ik}|$ and swaps row $k$ with that row. This ensures the multiplier is always $\le 1$, minimizing error growth.
• Complete Pivoting: Searches both the remaining rows and columns for the largest absolute element to use as the pivot. This involves swapping both rows and columns. While numerically more stable, the extensive search and bookkeeping make it computationally expensive and rarely used compared to partial pivoting.

The matrix $[A]$ is decomposed into a lower triangular matrix $[L]$ and an upper triangular matrix $[U]$.

The system $[A]\{x\} = \{B\}$ becomes $[L][U]\{x\} = \{B\}$. We can then solve for $\{d\}$ in $[L]\{d\} = \{B\}$ using forward substitution, and then solve for $\{x\}$ in $[U]\{x\} = \{d\}$ using back substitution.

There are specific algorithms for computing the LU factors:

• Doolittle's Method: Specifies that all diagonal elements of the lower triangular matrix $[L]$ must be $1$ (i.e., $l_{ii} = 1$).
• Crout's Method: Specifies that all diagonal elements of the upper triangular matrix $[U]$ must be $1$ (i.e., $u_{ii} = 1$).

If the matrix $[A]$ is symmetric and positive definite, it can be decomposed into a lower triangular matrix and its transpose. This method is highly efficient, requiring roughly $\frac{n^3}{6}$ operations, about half the execution time and storage of standard LU decomposition.

Any $m \times n$ matrix $[A]$ can be factored into three matrices.

SVD can easily compute the pseudoinverse of a matrix to solve least-squares problems and explicitly determine the rank, null space, and condition number of $[A]$ (where $\text{Cond}(A) = \sigma_{\text{max}}/\sigma_{\text{min}}$).

The Thomas algorithm is a highly efficient, simplified form of Gaussian elimination specifically designed for tridiagonal systems. It operates in two passes:

• Forward Elimination: Eliminates the lower diagonal elements.
• Backward Substitution: Solves for the unknowns starting from the last equation.

Because it avoids operations on known zero elements, the computational cost is strictly proportional to the number of equations ($O(n)$) rather than $O(n^3)$ for standard Gaussian elimination. This allows solving millions of equations in milliseconds.

A vector norm $||v||$ must satisfy basic scaling and triangle inequality rules. Common examples include:

• Euclidean Norm ($L_2$ norm): The standard physical length of a vector, defined as $\sqrt{\sum v_i^2}$.
• Sum Norm ($L_1$ norm): The sum of the absolute values of the elements, $\sum |v_i|$.
• Max Norm ($L_\infty$ norm): The single largest absolute value element in the vector, $\max |v_i|$.

• Row-Sum Norm ($||A||_{\infty}$): The maximum of the sums of the absolute values of the elements in each row.
• Column-Sum Norm ($||A||_1$): The maximum of the sums of the absolute values of the elements in each column.
• Spectral Norm ($||A||_2$): The square root of the largest eigenvalue of $A^TA$.

The formal Condition Number is defined as $\text{Cond}(A) = ||A|| \cdot ||A^{-1}||$. If $\text{Cond}(A) \approx 1$, the matrix is well-conditioned. If $\text{Cond}(A) \gg 1$, it is ill-conditioned.

Instead of storing $n^2$ elements, sparse matrix representations (like Compressed Sparse Row, CSR) store only the non-zero elements and their indices. This drastically reduces memory usage from $O(n^2)$ to $O(k)$ where $k$ is the number of non-zeros. Iterative methods (like Conjugate Gradient or Gauss-Seidel) are particularly well-suited for sparse systems because they only require matrix-vector multiplication, preserving the sparsity structure.

• Jacobi Method: Computes all new values $x_i^{k+1}$ using only the old values $x^k$ from the previous iteration.
• Gauss-Seidel Method: Uses the most recently computed values $x_j^{k+1}$ as soon as they are available, generally converging faster than the Jacobi method.

To accelerate the convergence of the Gauss-Seidel method, relaxation techniques apply a weighting factor $\omega$. If $1 < \omega < 2$, the method is called over-relaxation and accelerates convergence.