Two-person course project

Gram–Schmidt orthogonalisation: a numerical comparison

Shanghai University · Linear Algebra II course project (2022)

Implemented classical Gram–Schmidt (CGS) and the modified version (MGS) in MATLAB and C, compared the two orthonormal bases in Frobenius norm on ill-conditioned matrices and 100 random 100×100 matrices, and explained why formulas that are equivalent on paper separate in floating point.

Background

Gram–Schmidt orthogonalisation comes in two versions that are equivalent on paper:

  • Classical (CGS): each vector has all its projections subtracted at once;
  • Modified (MGS): each projection is applied immediately, and the updated vector is used for the next one.

In exact arithmetic both produce the same orthonormal basis. In floating point, the order of operations decides whether rounding errors are amplified by later steps. The project asked how large the difference is, when it appears, and why.

Chen Nuo and I completed the project: MATLAB implementations of both algorithms and the experiments, an independent C reproduction, and ill-conditioned and random matrices to quantify the gap.

The two algorithms

Classical Gram–Schmidt subtracts every projection in one pass:

u_k = v_k - Σ_{j<k} <v_k, u_j> u_j

The modified version splits the projections, updating the vector between them:

v_k ← v_k - <v_k, u_j> u_j,  j = 1..k-1

In code the difference is one index: CGS always uses the original column a(:,i) for the dot product, while MGS uses the already updated b(:,i). The whole experiment turns on that line.

Experimental design

  1. Run CGS and MGS on the same matrix to obtain Q_CGS and Q_MGS;
  2. measure the difference with the Frobenius norm ‖Q_CGS − Q_MGS‖_F;
  3. build an ill-conditioned matrix with a very small ε to amplify rounding errors;
  4. generate 100 random 100×100 matrices with cond > 10⁶, plot the condition-number/error curve, and repeat the experiment four times.

Results

MatrixSizecond(A)‖Q_CGS − Q_MGS‖_F
A = [[1,2,3],[2,−1,2],[1,1,2]]3×353.945.92×10⁻³¹ (numerically zero)
B = [[1,1,1],[ε,0,0],[0,ε,0],[0,0,ε]], ε = 10⁻¹⁰4×31.73×10¹⁰0.2679

The conclusions are direct:

  • for a small condition number the two algorithms agree numerically;
  • at a very large condition number the columns are nearly linearly dependent, cancellation in the projection becomes severe, the CGS error is amplified from step to step, while the MGS error stays local to each projection;
  • MGS is therefore numerically more stable, which is why numerical libraries use MGS (or Householder QR).

C implementation

main.c turns the algorithm into an executable: produitscalaire computes a dot product, norme1 normalises, and the main loop orthonormalises column by column. The input is the number of columns, the number of rows, then the matrix row by row; the current implementation requires a square matrix of at most 100×100.

gcc -O2 -Wall -o gs main.c -lm
printf "3 3\n1 2 3\n2 -1 2\n1 1 2\n" | ./gs

The output matches MATLAB’s Q. The code deliberately transposes on input and output — it stores a[j][i] — so that each column is contiguous in memory and the column-vector loops have a natural access order.

Limitations

  • square matrices only, at most 100×100;
  • no column pivoting and no reorthogonalisation, so linearly dependent columns divide by zero or produce a meaningless basis;
  • the C version implements CGS, not MGS; replacing a[i] with b[i] in the dot product gives MGS, but the repository keeps the classical version used in the report.

For real computation, Householder QR is the safer choice, or Gram–Schmidt followed by a reorthogonalisation pass.

MATLAB scripts, C implementation, French report and experiment figures: https://github.com/yicongl1/Linear-Algebra-Gram-Schmidt

Technical notes

01 Classical versus modified Gram–Schmidt: why equivalent formulas differ by more than ten orders of magnitude Projection order, cancellation and condition number: from a 3×3 numerical zero to 0.2679 at cond 10¹⁰, on to 100 random ill-conditioned matrices. 02 Writing Gram–Schmidt in C: dot products, normalisation and column-major thinking in 49 lines Transposed input, column storage, the produitscalaire and norme1 helpers, and how to match the MATLAB output exactly.

Related skills

  • MATLAB
  • Academic writing