OWL ONLINE TUTORIALFROM THE BOOK OCAML SCIENTIFIC COMPUTING

CHAPTER 04

Linear Algebra

Linear algebra is an important area of mathematics and has many applications in numerical computing. In this chapter we first present an overview, and then focus on how to use OCaml to solve concrete problems and develop a thorough understanding of the key concepts in linear algebra. This chapter covers the classic topics in linear algebra, including Gaussian elimination, vector spaces, determinants, eigenvalues and eigenvectors. Before discussing these topics, we provide a brief introduction to the matrix data structure supported in OCaml.

4.1 Vectors and Matrices

Linear algebra is about solving systems of linear equations expressed in vectors and matrices, hence we begin by familiarising ourselves with these basic elements. The dense matrix functions can be accessed from the Dense.Matrix module, with support for four number types: single, double, complex single, and complex double in the Matrix.S, Matrix.D, Matrix.C and Matrix.Z modules respectively. The Mat module is an alias of Matrix.D provided for convenience. Except for a handful of functions (e.g., re to extract the real part of complex elements) most are shared by these four sub-modules. Vectors can be represented as one-row or one-column matrices. We will briefly discuss sparse matrix storage in the last section.

There are multiple functions to help create matrices with certain contents. For example, the following functions all create various 5x5 matrices:

  • Mat.empty 5 5, a matrix with uninitialised elements
  • Mat.create 5 5 2., a matrix with all elements initialised to 2
  • Mat.zeros 5 5, a matrix of all zeros
  • Mat.ones 5 5, a matrix of all ones
  • Mat.eye 5, an identity matrix
  • Mat.magic 5, a magic square matrix
  • Mat.uniform 5 5, a random matrix of uniform distribution
  • Mat.uniform_int 5 5, a random matrix with integer-valued elements
  • Mat.sequential 5 5, a matrix of sequential integers
  • Mat.semidef 5, a random positive semidefinite matrix
  • Mat.gaussian 5 5, a random Gaussian matrix
  • Mat.bernoulli 5 5, a random Bernoulli matrix

In addition, to build a matrix from an OCaml array, use the of_array operation, e.g., Mat.of_array [1.;2.;3.—] 1 3— builds a matrix of size 1x3.

The Mat module supports many mathematical operations on two matrices x and y. For example, the matrix product Mat.dot x y can also be written Mat.(x *@ y), and element-wise addition Mat.add x y can be Mat.(x + y). The approximate element-wise equality comparison Mat.approx_equal can be used as Mat.(x =~ y). Of course, these operations are all available for the other precisions, namely in the Matrix.S/C/Z sub-modules.

If you perform operations between a matrix and a scalar value, you need to be careful about their order. Assuming a is a float scalar value, we can add it to each element in matrix x using Mat.(x +$ a) or Mat.(a $+ x). Note the difference between these two operators, which have corresponding long names Mat.add_scalar and Mat.scalar_add respectively.

There are other ready-made mathematical functions such as Mat.abs (absolute value) and Mat.l2norm’, where the ’ in the name indicates that the result is a scalar value rather than a 1x1 matrix. The matrix module also contains operations such as concatenation (Mat.concat) and transpose (Mat.transpose).

Finally, another key matrix operation is to index elements of the matrix, supported via get and set to retrieve and modify elements by specifying zero-based row and column indices, e.g.,

OCAML
let x = Mat.uniform 5 5;;
Mat.set x 1 2 0.;;
let a = Mat.get x 0 3;;

The second line sets the element at (1,2) to 0, and then gets the value of the element at (0,3). For dense matrices we can also use shorthand .%{i; j} to access elements, rewriting the code above as:

OCAML
Mat.(x.%{1;2} <- 0.);;
let a = Mat.(x.%{0;3});;

Matrix modifications using set are in-place. We can retrieve rows from a matrix x by the rows function. The selected rows will be used to assemble a new matrix. We can select columns similarly using cols.

This section provides a very brief introduction to the matrix module and the functions that will be used in the rest of this chapter. The matrix module builds on the Ndarray (N-dimensional array) module, enabling matrices and ndarrays in Owl to inter-operate. The Ndarray module and its functions, and thus the Matrix module, are discussed in Chap. 5.

The rest of this chapter makes use of the Linalg module that provides various high-level linear algebra APIs. As with the matrix module, it supports both real and complex numbers in single and double precision. The Linalg.Generic module provides the operations underlying Linalg.S/D/C/Z; some functions require explicit output-type information. In this chapter, we will show how to use different aspects of this module to investigate linear algebra topics.

4.2 Gaussian Elimination

Solving systems of linear equations is a core problem in linear algebra and is frequently encountered in scientific computation [1]. Gaussian Elimination is a classic method to do this, and it can work surprisingly well in modern numerical libraries [2]. Here is a simple example:

2x1 + 2x2 + 2x3 = 4 2x1 + 2x2 + 3x3 = 5 3x1 + 4x2 + 5x3 = 7 (4.1)

Divide the first equation by 2:

x1 + x2 + x3 = 2 2x1 + 2x2 + 3x3 = 5 3x1 + 4x2 + 5x3 = 7 (4.2)

Multiply the first equation by -2 and add it to the second. Then multiply the first equation by -3 and add it to the third. This gives us Eq. 4.3.

x1 + x2 + x3 = 2 x3 = 1 x2 + 2x3 = 1 (4.3)

x1 + x2 + x3 = 2 x2 + 2x3 = 1 x3 = 1 (4.4)

Finally, swapping the second and third, we get Eq. 4.4. We thus have x3 = 1, and can substitute for x3 in the second equation to obtain x2 = −1. Plug both back to the first equation and we have x1 = 2.

This process demonstrated the basic operations of Gaussian elimination: eliminate unknown variables until the system of linear equations is easy to solve, and then back-substitute. There are three basic row operations we use: multiplying a row by a non-zero scalar, adding a multiple of one row to another, and swapping two rows. The starting equation Eq. 4.1 can be more concisely expressed with vectors:

x1 [ 2 2 3 ]+x2 [ 2 2 4 ]+x3 [ 2 3 5 ] = [ 4 5 7 ]

or in the form 𝐴𝑥 = b using matrix notation:

[ 2 2 2 2 2 3 3 4 5 ] [ x1 x2 x3 ] = [ 4 5 7 ]⟹ [ x1 x2 x3 ] = [ 2 −1 1 ]

Here A is a matrix, b is a column vector, and x is the unknown vector we are solving for. Matrix notation is often used to describe systems of linear equations concisely.

4.2.1 LU Factorisation

Let’s look again at the Gaussian elimination example above. The final form Eq. 4.4 can be expressed with the matrix notation as:

[ 1 1 1 0 1 2 0 0 1 ]

As we can see, all the elements below the diagonal of the square matrix are zero. Such a matrix is an upper triangular matrix, usually denoted U. Similarly, a square matrix where all the elements above the diagonal are zero is a lower triangular matrix, denoted L. We can use is_triu and is_tril in the Linalg module to test for triangularity. In nonsingular square elimination, the diagonal entries of U are the pivots. The i-th pivot is the coefficient used to eliminate the i-th variable at step i, before any row normalisation.

When no row exchanges are needed, a square matrix can be factorised into a product of lower and upper triangular matrices:

A = 𝐿𝑈, (4.5)

and this process is called the LU factorisation. This embodies the process of Gaussian elimination. Consider again the initial problem of solving the linear equation 𝐴𝑥 = b. One reason the LU factorisation is important is that if matrix A in 𝐴𝑥 = b is triangular, then solving it becomes straightforward, as seen in the previous example. We can use the triangular_solve function in Linalg to efficiently solve the linear equations if we already know that the matrix is triangular.

For a nonsingular square matrix with A = 𝐿𝑈, we can change 𝐴𝑥 = b to 𝐿𝑈𝑥 = b. First we find a column vector c so that 𝐿𝑐 = b, then we can find x so that 𝑈𝑥 = c. Both sets of triangular equations are easy to solve. The lu function performs LU factorisation with pivoting. Use the previous example once more:

OCAML SESSION
# let a = [|
      2.;2.;2.;
      2.;2.;3.;
      3.;4.;5.;|];;
val a : float array = [|2.; 2.; 2.; 2.; 2.; 3.; 3.; 4.; 5.|]
# let a = Mat.of_array a 3 3;;
val a : Owl.Mat.mat =
   C0 C1 C2
R0  2  2  2
R1  2  2  3
R2  3  4  5
OCAML SESSION
# let l, u, p = Linalg.D.lu a;;
val l : Owl.Linalg.D.mat =

         C0 C1 C2
R0        1  0  0
R1 0.666667  1  0
R2 0.666667  1  1

val u : Owl.Linalg.D.mat =

   C0        C1        C2
R0  3         4         5
R1  0 -0.666667 -0.333333
R2  0         0        -1

val p : Owl.Linalg.D.int32_mat =
   C0 C1 C2
R0  3  2  3
# let lu_pivots = p;;
val lu_pivots : Owl.Linalg.D.int32_mat =
   C0 C1 C2
R0  3  2  3

The first two returned matrices are the lower and upper triangular factors. However, if we multiply them without accounting for the pivoting, the result differs from the original matrix:

OCAML SESSION
# let a' = Mat.dot l u;;
val a' : Owl.Mat.mat =
   C0 C1 C2
R0  3  4  5
R1  2  2  3
R2  2  2  2

It turns out that we need to account for row exchanges to obtain the correct answer. Pivoting avoids zero pivots where possible and, for numerical stability, may exchange rows even when a pivot is non-zero. This process is called pivoting. It is closely related to the stability of numerical computation. Choosing improper pivots can lead to incorrect solutions [3]. Pivoting can be expressed as a permutation matrix P with the same rows as the identity matrix, each row and column having just a single 1 element. The full LU factorisation can thus be expressed as:

𝑃𝐴 = 𝐿𝑈
OCAML SESSION
# let p = Mat.of_array [|
      0.;0.;1.;
      0.;1.;0.;
      1.;0.;0.;
    |] 3 3;;
val p : Owl.Mat.mat =
   C0 C1 C2
R0  0  0  1
R1  0  1  0
R2  1  0  0
# Mat.(dot p a =~ dot l u);;
- : bool = true

Recall that the lu function also has a third output, the pivot vector p, which contains the one-based LAPACK pivot indices [|3;2;3|]. We save it as lu_pivots before reusing the name p for the manual permutation matrix. How do we translate it to the previous permutation matrix? Each element pi records the row exchanged with row i at that elimination step. Subtract one from each pivot index for OCaml’s zero-based indexing, and apply the row exchanges in forward order to the identity matrix. This gives the permutation matrix P in 𝑃𝐴 = 𝐿𝑈:

OCAML
let perm_vec_to_mat vec =
  let n = Array.length vec in
  let permutation = Mat.eye n in
  Array.iteri (fun i pivot ->
    let j = pivot - 1 in
    if j < 0 || j >= n then invalid_arg "one-based LU pivot";
    for column = 0 to n - 1 do
      let value = Mat.get permutation i column in
      Mat.set permutation i column (Mat.get permutation j column);
      Mat.set permutation j column value
    done
  ) vec;
  permutation;;
let pivot_vector = Dense.Matrix.Generic.to_array lu_pivots
  |> Array.map Int32.to_int;;
let permutation = perm_vec_to_mat pivot_vector;;
Mat.(dot permutation a =~ dot l u);;

Note that there is more than one way to perform LU factorisation. For example, for the same matrix, a different pivot choice gives another factorisation:

[ 1 0 0 0 0 1 0 1 0 ] [ 2 2 2 2 2 3 3 4 5 ] = [ 1 0 0 1.5 1 0 1 0 1 ] [ 2 2 2 0 1 2 0 0 1 ]

4.2.2 Inverse and Transpose

The concept of an inverse matrix is related to the identity matrix In, which is built via Mat.eye n where n is the size of the square matrix. The identity matrix is a special form of Diagonal Matrix, a square matrix whose non-zero elements occur only on its diagonal. We can check if a matrix is diagonal with the is_diag function.

OCAML SESSION
# Mat.eye 5 |> Linalg.D.is_diag;;
- : bool = true

The inverse of an n × n square matrix A is denoted as A−1 so that

AA−1 = I n. (4.6)

Not all square matrices have inverses. There are many necessary and sufficient conditions that indicate if A is invertible. One is that elimination produces n non-zero pivots.

We use the function inv to perform matrix inversion. It is straightforward to verify the result according to the definition. The example uses semidef, which generates a matrix of the form BTB. Such a matrix is positive semidefinite, but is invertible only if B has full column rank; the recorded sample is invertible.

OCAML SESSION
# let x = Mat.semidef 5 in
    let y = Linalg.D.inv x in
    Mat.(x *@ y =~ eye 5);;
- : bool = true

Another frequently used operation is to take the transpose of a matrix. Denoted as AT, its i-th row is taken from the i-th column of the original matrix A. It has properties such as

(𝐴𝐵)T = BT AT. (4.7)

We can verify this property using the matrix function Mat.transpose.

OCAML SESSION
# let flag =
      let a = Mat.uniform 4 4 in
      let b = Mat.uniform 4 4 in
      let m1 = Mat.(dot a b |> transpose) in
      let m2 = Mat.(dot (transpose b) (transpose a)) in
      Mat.(m1 =~ m2);;
val flag : bool = true

Finally, a related special class of matrices is the Symmetric Matrix, those matrices equal to their own transpose. This can be verified using the is_symmetric function.

4.3 Vector Space

We have discussed solving the linear equations 𝐴𝑥 = b using Gaussian elimination where A is a square matrix. We now discuss further how to determine whether there are any solutions and whether a solution is unique. To answer such questions, we need to be familiar with the concept of a vector space.

The vector space ℝn contains all column vectors with n real elements. Its operations are vector addition and multiplication by real scalars. A linear combination is a sum of scalar multiples of vectors. A subspace is a non-empty subset closed under these operations: any linear combination of its vectors stays in the same subset.

There are four fundamental subspaces of interest when solving linear systems 𝐴𝑥 = b where A is a real m by n matrix. The column space, a subspace of ℝm, is all linear combinations of the columns of A. Similarly, the row space consists of all linear combinations of the rows of A, viewed as vectors in ℝn. The nullspace N(A) contains all the vectors x such that 𝐴𝑥 = 0. It is a subspace of ℝn. The left nullspace is the nullspace of AT, a subspace of ℝm.

4.3.1 Rank and Basis

When discussing Gaussian elimination above, we assumed an ideal situation: matrix A is an n × n square matrix for which there exists a unique solution. But that is not always the case. A may not even be a square matrix. When m < n, a consistent system cannot have a unique solution; when m > n, a system may be inconsistent. Besides, even when A is a square matrix, the information contained in one equation might be repeated in another if, for example, one equation is simply a multiple of another. Applying Owl’s LU routine to the following singular matrix produces a failure:

OCAML SESSION
# let x = Mat.of_array [|
    1.; 2.; 3.;
    0.; 0.; 1.;
    0.; 0.; 2.;
  |] 3 3;;
val x : Owl.Mat.mat =
   C0 C1 C2
R0  1  2  3
R1  0  0  1
R2  0  0  2
# let singular_lu_rejected =
    try ignore (Linalg.D.lu x); false
    with Failure _ -> true;;
val singular_lu_rejected : bool = true

This indicates a zero pivot in the second column. The matrix is singular, and this Owl call rejects it; the example catches that expected failure. A singular matrix may still have an LU factorisation, but its triangular factors cannot provide an invertible solve. As can be seen in this example, we cannot expect linear algebra functions to work without checking their assumptions.

To determine the solutions to a general 𝐴𝑥 = b, we must understand the concept of rank, the number of non-zero pivots in row-echelon form. For a more intuitive understanding of rank, we introduce the concept of linear independence. In a linear combination ∑ ⁡ i=1ncivi where vi are vectors and ci are scalars, if ∑ ⁡ i=1ncivi = 0 only occurs when ci = 0 for all i, vectors v1,v2,…,vn are linearly independent. The rank of a matrix is the maximum number of linearly independent rows. We can understand rank as the number of “effective” rows in the matrix. As an example, we can check the rank of the previous matrix with Linalg.D.rank x. The result 2 indicates only two effective rows, so this three-variable system cannot have a unique solution.

An application of rank produces a key concept in linear algebra: basis. A sequence of vectors is a basis of a vector space or subspace if the vectors are linearly independent, and all vectors in the space can be represented as a linear combination of vectors in the basis. A space can have infinitely many bases, but the number of vectors in each basis is the same and is called the dimension of the vector space. For example, if an m × n matrix A has rank r, then the dimension of its null space is n − r, and the dimension of its column space is r. For a matrix with full column rank r = n, its columns form a basis of its column space, and its null space has dimension zero, so the only solution of 𝐴𝑥 = 0 is the zero vector.

4.3.2 Orthogonality

We can relate the basis of a vector space to the Cartesian coordinate system in (for example) a three-dimensional space where every vector in the space can be represented in terms of values on the three axes, x, y and z. There are many such basis sets but the set {x = (1,0,0), y = (0,1,0), z = (0,0,1) } is convenient because all members are mutually orthogonal, simplifying many problems.

Orthogonality also applies to subspaces. Two real vectors a and b are orthogonal if aTb = 0, and we can say two subspaces A and B are orthogonal if every vector in A is orthogonal to every vector in B. For example, the nullspace and row space of a real matrix are orthogonal.

Among the bases of a subspace, one in which every vector is perpendicular to every other is called an orthogonal basis. Moreover, if the length of each vector is normalised to one unit, it is an orthonormal basis. A real square matrix whose columns form an orthonormal basis is an orthogonal matrix. The null function returns a matrix X whose columns form an orthonormal basis for the null space, so 𝐴𝑋 = 0.

OCAML SESSION
# let a = Mat.magic 4;;
val a : Owl.Mat.mat =

   C0 C1 C2 C3
R0  1 15 14  4
R1 12  6  7  9
R2  8 10 11  5
R3 13  3  2 16
# let x = Linalg.D.null a;;
val x : Owl.Linalg.D.mat =

          C0
R0 -0.223607
R1  -0.67082
R2   0.67082
R3  0.223607
# Mat.dot a x |> Mat.l2norm';;
- : Owl.Mat.elt = 4.48851511774729321e-15

Having defined orthogonal and orthonormal bases, how do we build them? The QR Factorisation decomposes a real matrix A as A = 𝑄𝑅. For a reduced factorisation with m ≥ n, Q has orthonormal columns and R is upper triangular; if A has full column rank, the columns of Q form a basis of its column space. It is provided in the linear algebra module as the qr function, returning Q, R, and column pivot indices. The default value of pivot is false, in which case the third result is empty. Setting it to true performs a column-pivoted factorisation 𝐴𝑃 = 𝑄𝑅, with P represented by one-based column indices.

OCAML SESSION
# let a = Mat.of_array [|
      12.; -51.;   4.;
       6.; 167.; -68.;
      -4.;  24.; -41.;
    |] 3 3;;
val a : Owl.Mat.mat =

   C0  C1  C2
R0 12 -51   4
R1  6 167 -68
R2 -4  24 -41
# let q, r, _ = Linalg.D.qr a;;
val q : Owl.Linalg.D.mat =

          C0        C1         C2
R0 -0.857143  0.394286   0.331429
R1 -0.428571 -0.902857 -0.0342857
R2  0.285714 -0.171429   0.942857

val r : Owl.Linalg.D.mat =

    C0   C1  C2
R0 -14  -21  14
R1   0 -175  70
R2   0    0 -35

4.3.3 Solving Ax = b

We can now discuss the general solution structure of 𝐴𝑥 = 0 and 𝐴𝑥 = b where A is again an m × n matrix. There are non-zero solutions to 𝐴𝑥 = 0 if and only if the rank r(A) < n. The nullspace then has dimension n − r, and its n − r orthonormal basis vectors can be found with the null function. For example:

OCAML SESSION
# let a = Mat.of_array [|
      1.; 5.;-1.;-1.;
      1.;-2.; 1.; 3.;
      3.; 8.;-1.; 1.;
      1.;-9.; 3.; 7.;
    |] 4 4;;
val a : Owl.Mat.mat =

   C0 C1 C2 C3
R0  1  5 -1 -1
R1  1 -2  1  3
R2  3  8 -1  1
R3  1 -9  3  7
# Linalg.D.rank a;;
- : int = 2

This is a rank 2 matrix, so the nullspace has dimension 4 − 2 = 2 and the function returns two basis vectors:

OCAML SESSION
# Linalg.D.null a;;
- : Owl.Linalg.D.mat =

          C0        C1
R0 -0.851419 0.0136382
R1  0.273706  0.143885
R2 0.0762491  0.962526
R3   0.44086 -0.229465

These two vectors form a fundamental system of solutions of 𝐴𝑥 = 0. All solutions are their linear combinations; using the rounded coordinates displayed above, we write:

x ≈ c1 [ −0.851419 0.273706 0.0762491 0.44086 ]+c2 [ 0.0136382 0.143885 0.962526 −0.229465 ] (4.8)

Here c1 and c2 can be any constant scalars. Considering the general form 𝐴𝑥 = b where b is an m × 1 vector, there exists just one solution if and only if r(A) = r([A,b]) = n where [A,b] is a matrix formed by concatenating A and b along the column. If r(A) = r([A,b]) < n, 𝐴𝑥 = b has an infinite number of solutions with the general form:

x0 + c1x1 + c2x2 + … + ckxk (4.9)

where x0 is a particular solution to 𝐴𝑥 = b, and x1,x2,…,xk form a basis of the nullspace, with k = n − r(A). If r(A)≠r([A,b]), the system has no solution.

The function linsolve a b solves linear systems and least-squares problems of the form 𝐴𝑋 = B. By default, it uses LU factorisation with partial pivoting for a nonsingular square a. For a rectangular full-rank matrix, it uses LAPACK’s QR or LQ least-squares solver. The number of rows of a must equal the number of rows of b. For a square triangular matrix, explicitly set typ:‘u or typ:‘l to select triangular_solve; the default does not detect triangularity. The following matrix is rank deficient, so we instead use its pseudoinverse to obtain a minimum-norm particular solution.

OCAML SESSION
# let a = Mat.of_array [|
       2.; 3.; 1.;
       1.;-2.; 4.;
       3.; 8.;-2.;
       4.;-1.; 9.;
    |] 4 3;;
val a : Owl.Mat.mat =

   C0 C1 C2
R0  2  3  1
R1  1 -2  4
R2  3  8 -2
R3  4 -1  9
# let b = Mat.of_array [|4.;-5.;13.;-6.|] 4 1;;
val b : Owl.Mat.mat =
   C0
R0  4
R1 -5
R2 13
R3 -6
# let x0 = Mat.dot (Linalg.D.pinv a) b;;
val x0 : Owl.Mat.mat =

          C0
R0  0.333333
R1   1.33333
R2 -0.666667

Then we use null to find a basis of the nullspace. You can verify that matrix a is of rank 2, so the basis for 𝐴𝑥 = 0 contains 3 − 2 = 1 vector.

OCAML SESSION
# let x1 = Linalg.D.null a;;
val x1 : Owl.Linalg.D.mat =

          C0
R0 -0.816497
R1  0.408248
R2  0.408248

So the solutions to 𝐴𝑥 = b can be expressed as:

[ 1∕3 4∕3 −2∕3 ]+c1 [ −2 1 1 ],c1 ∈ ℝ.

An important takeaway from this chapter is that using these functions in Linalg requires a solid background in linear algebra. Blind application of them can easily lead to wrong or misleading answers.

4.3.4 Matrix Sensitivity

The sensitivity of a linear system is crucial in numerical computation: in 𝐴𝑥 = b, how much can x vary if we change A or b slightly? The Condition Number measures this sensitivity for a nonsingular square coefficient matrix [4].

First we need to understand the Norm, here the induced 2-norm of a real matrix ∥A∥2, calculated as the square root of the maximum eigenvalue of ATA. (The concept of eigenvalue will be introduced in Sec. 4.5.) This matrix norm gives an upper bound so that for any x we have:

∥𝐴𝑥∥≤∥A∥∥x∥. (4.10)

Here ∥𝐴𝑥∥ and ∥x∥ indicate the Euclidean vector norm, and ∥A∥ denotes the induced 2-norm. It bounds how much A can amplify the input x; relative sensitivity also involves A−1. We can calculate this matrix norm using Linalg.D.norm, whose default is p = 2; it differs from the Frobenius norm returned by Mat.l2norm’.

The most frequently used condition number is that representing the sensitivity of inverse matrix [5]. Under the definition of norm, the condition number for inversion of a matrix can be expressed as ∥A∥∥A−1∥, and calculated using the cond function. Let’s look at an example:

OCAML SESSION
# let a = Mat.of_array [|
      4.1; 2.8;
      9.7; 6.6;
    |] 2 2;;
val a : Owl.Mat.mat =
    C0  C1
R0 4.1 2.8
R1 9.7 6.6
# let c = Linalg.D.cond a;;
val c : float = 1622.99938385651058

Its condition number for inversion is much larger than one, so a small change in A can lead to a large relative change in A−1. Let’s look at one such perturbation.

OCAML SESSION
# let a' = Linalg.D.inv a;;
val a' : Owl.Linalg.D.mat =
    C0  C1
R0 -66  28
R1  97 -41

Changing the last row of the matrix slightly and recalculating gives:

OCAML SESSION
# let a2 = Mat.of_array [|
       4.1;   2.8;
      9.67; 6.607;
    |] 2 2;;
val a2 : Owl.Mat.mat =
     C0    C1
R0  4.1   2.8
R1 9.67 6.607
# let a2' = Linalg.D.inv a2;;
val a2' : Owl.Linalg.D.mat =

         C0       C1
R0  520.236 -220.472
R1 -761.417  322.835

As the large condition number warns, this small change to a causes a large change in its inverse. The solution of 𝐴𝑥 = b can also be sensitive, depending on the right-hand side and the perturbation.

4.4 Determinants

Besides pivots, another basic quantity in linear algebra is the determinant. An important application is to characterise whether a square matrix A is invertible or singular. For an n × n matrix, det ⁡ (A)≠0 if and only if rank ⁡ (A) = n, i.e., A is invertible. This is an exact-arithmetic statement; a floating-point determinant alone is not a reliable test for near-singularity.

For a square matrix A:

[ a11 a12 … a1n a21 a22 … a2n ⋮ ⋮ … ⋮ a n1 an2 … a𝑛𝑛 ]

its determinant det ⁡ (A) is defined as:

∑ j1j2…jn(−1)τ(j1j2…jn)a 1j1a2j2…anjn

The sum is over all permutations (j1,…,jn) of (1,…,n). Here τ(j1j2…jn) = i1 + i2 + … + in−1, where ik counts the indices p > k for which jp < jk. Mathematically, there are many techniques that can be used to simplify this calculation [6]. But as far as this book is concerned, it is sufficient for us to use the det ⁡ function to calculate the determinant of a matrix.

We can also use it to understand the solution of 𝐴𝑥 = b. If det ⁡ (A)≠0, 𝐴𝑥 = b has one and only one solution. This theorem is part of Cramer’s rule, and these properties are widely used when finding eigenvalues, discussed next.

When the determinant is positive and we need its logarithm, we can use logdet. It sums logarithms of LU diagonal magnitudes rather than forming their product, reducing the risk of overflow or underflow. The real-valued Owl routine rejects negative determinants and singular inputs; it is not a general zero-determinant test.

OCAML SESSION
# let x = Mat.magic 5;;
val x : Owl.Mat.mat =

   C0 C1 C2 C3 C4
R0 17 24  1  8 15
R1 23  5  7 14 16
R2  4  6 13 20 22
R3 10 12 19 21  3
R4 11 18 25  2  9
# Linalg.D.det x;;
- : Owl.Linalg.D.elt = 5070000.
# Linalg.D.logdet x;;
- : Owl.Linalg.D.elt = 15.4388513755673671

4.5 Eigenvalues and Eigenvectors

In this section we move from studying 𝐴𝑥 = b to 𝐴𝑥 = 𝜆𝑥. The pattern

𝐴𝑥 = 𝜆𝑥 (4.11)

frequently appears in scientific and engineering analyses describing the change of a dynamic system over time [7]. For an n × n square matrix, if there exists a scalar λ and a non-zero column vector x satisfying:

(𝜆𝐼 − A)x = 0, (4.12)

then λ is an eigenvalue of A, and x is its corresponding eigenvector. To find the eigenvalues of a matrix A, we must find the roots of the determinant of 𝜆𝐼 − A. det ⁡ (𝜆𝐼 − A) = 0 is the characteristic equation of A. For example, for matrix

A = [ 3 1 0 −4 −1 0 4 −8 2 ]

Its characteristic matrix 𝜆𝐼 − A is:

[ λ − 3 −1 0 4 λ + 1 0 −4 8 λ − 2 ]

By the definition of determinant, det ⁡ (𝜆𝐼 − A) = (λ − 1)2(λ − 2) = 0.

An n-degree characteristic polynomial has n complex roots counted with algebraic multiplicity. Specifically, here we have λ1 = 1,λ2 = 1,λ3 = 2. Substituting λ1 into Eq. 4.12 gives (I − A)x = 0. Therefore, we can find a basis for the nullspace of I − A with:

OCAML SESSION
# let basis =
      let ia = Mat.((eye 3) - (of_array
        [|3.; 1.;0.;
         -4.;-1.;0.;
          4.;-8.;2.|] 3 3))
      in
      Linalg.D.null ia;;
val basis : Owl.Linalg.D.mat =

           C0
R0 -0.0496904
R1  0.0993808
R2   0.993808

We thus get a fundamental solution x0 = [−0.05,0.1,1]T.

Similarly, the eigenvectors for the eigenvalue 2 are the non-zero scalar multiples of [0,0,1]T.

We can use the function eig to compute the right eigenvectors v and eigenvalues w of an arbitrary square matrix x. The eigenvectors are column vectors in v, their corresponding eigenvalues have the same order in w as that in v.

OCAML SESSION
# let eigvec, eigval =
      let a = Mat.of_array [|
          3.; 1.;0.;
         -4.;-1.;0.;
          4.;-8.;2.;
      |] 3 3 in
      Linalg.D.eig a;;
val eigvec : Owl.Linalg.D.complex_mat =

        C0               C1               C2
R0 (0, 0i)  (0.0496904, 0i)  (0.0496904, 0i)
R1 (0, 0i) (-0.0993808, 0i) (-0.0993808, 0i)
R2 (1, 0i)  (-0.993808, 0i)  (-0.993808, 0i)

val eigval : Owl.Linalg.D.complex_mat =

        C0      C1      C2
R0 (2, 0i) (1, 0i) (1, 0i)

Note that the results are expressed as complex numbers. To get just the eigenvalues, we can use the eigvals function. Both functions take boolean arguments permute and scale indicating whether the input matrix should be permuted or diagonally scaled.

4.5.1 Complex Matrices

As in the previous examples, complex matrices are frequently used in calculating eigenvalues and eigenvectors, so we next re-introduce some concepts in complex spaces.

The notion of a symmetric matrix can be extended to the complex domain as the Hermitian Matrix. A matrix A is Hermitian if A = AH, where AH denotes its conjugate transpose: when transposing, each element a + 𝑏𝑖 becomes its complex conjugate a − 𝑏𝑖. The is_hermitian function tests if a matrix is Hermitian, as in the example below.

OCAML SESSION
# let a = Dense.Matrix.Z.of_array [|
      {re=1.; im=0.}; {re=2.; im=(-1.)};
      {re=2.; im=1.}; {re=3.; im=0.};
    |] 2 2;;
val a : Owl.Dense.Matrix.Z.mat =

        C0       C1
R0 (1, 0i) (2, -1i)
R1 (2, 1i)  (3, 0i)
# Linalg.Generic.is_hermitian a;;
- : bool = true

The conj function performs element-wise conjugation. Combining it with transpose gives the conjugate transpose:

OCAML SESSION
# Dense.Matrix.Z.(conj a |> transpose);;
- : Owl.Dense.Matrix.Z.mat =

         C0       C1
R0 (1, -0i) (2, -1i)
R1  (2, 1i) (3, -0i)

It can be shown that if a matrix A is Hermitian, for all complex vectors x, xH𝐴𝑥 is real as are all its eigenvalues.

OCAML SESSION
# Linalg.Z.eigvals a;;
- : Owl.Linalg.Z.complex_mat =

                         C0                      C1
R0 (-0.44949, 1.50231E-17i) (4.44949, 2.07021E-16i)

Related to the Hermitian matrix is the Unitary Matrix, a complex square matrix U such that

UHU = I. (4.13)

The inverse and conjugate transpose of U are equal; unitary matrices are the complex analogue of real orthogonal matrices.

4.5.2 Similarity Transformation and Diagonalisation

For an n × n matrix A, and an invertible n × n matrix M, the matrix

B = M−1𝐴𝑀 (4.14)

is said to be similar to A, and B has the same eigenvalues as A. M can be thought of as a matrix that changes basis while A is a linear transformation, so M−1𝐴𝑀 first changes the basis before applying the linear transformation and changing the basis back. For example, in a three-dimensional space, M may have three linearly independent vectors as its columns, expressed in the standard basis [1,0,0]T, [0,1,0]T, [0,0,1]T. Choosing a suitable basis can simplify the matrix representing the transformation. Finding a suitable similar matrix is thus key to simplifying calculations in many scientific and engineering problems.

One type of possible simplification is to find a triangular matrix that is similar. The Schur decomposition theorem states that a complex square matrix A can be written as 𝑈𝑇UH, where U is unitary and T is upper triangular. A real Schur factorisation instead uses an orthogonal matrix and an upper quasi-triangular matrix with 1 × 1 and 2 × 2 diagonal blocks. The complex decomposition can be computed using schur as below:

OCAML SESSION
# let a = Dense.Matrix.Z.of_array [|
      {re=1.; im=0.};    {re=1.; im=0.};
      {re=(-2.); im=0.}; {re=3.; im=0.};
    |] 2 2;;
val a : Owl.Dense.Matrix.Z.mat =

         C0      C1
R0  (1, 0i) (1, 0i)
R1 (-2, 0i) (3, 0i)
# let t, u, eigvals = Linalg.Z.schur a;;
val t : Owl.Linalg.Z.mat =

        C0                    C1
R0 (2, 1i) (2.10381, -0.757614i)
R1 (0, 0i)              (2, -1i)

val u : Owl.Linalg.Z.mat =

                       C0                      C1
R0 (-0.408248, 0.408248i)  (0.563384, -0.590987i)
R1        (-0.816497, 0i) (-0.577185, 0.0138014i)

val eigvals : Owl.Linalg.Z.complex_mat =

        C0       C1
R0 (2, 1i) (2, -1i)

The returned result t is upper triangular, and u is unitary, verified as follows:

OCAML SESSION
# Dense.Matrix.Z.(dot u (conj u |> transpose));;
- : Owl.Dense.Matrix.Z.mat =

                             C0                          C1
R0                      (1, 0i) (7.63278E-17, 3.38271E-17i)
R1 (7.63278E-17, -3.38271E-17i)                     (1, 0i)

Another very important similarity transformation is diagonalisation. Suppose A has n linearly independent eigenvectors that are the columns of a matrix Q, then Q−1𝐴𝑄 is a diagonal matrix Λ, and the eigenvalues of A are the diagonal elements of Λ. Equivalently,

A = QΛQ−1 (4.15)

is the Eigen Decomposition. Analysing A’s diagonal similar matrix Λ rather than A directly often greatly simplifies problems.

Note that not every matrix can be diagonalised. If none of the n eigenvalues of A are equal, then corresponding eigenvectors are linearly independent and A can be diagonalised over the complex numbers. In particular, every real symmetric matrix can be diagonalised by an orthogonal matrix, and every Hermitian matrix by a unitary matrix.

4.6 Positive Definite Matrices

We now introduce the Positive Definite Matrix, unifying the three key ideas introduced so far: pivots, determinants, and eigenvalues.

4.6.1 Positive Definiteness

A real matrix is Positive Definite if it is symmetric and

xT𝐴𝑥 > 0 (4.16)

for all non-zero vectors x. There are several necessary and sufficient conditions that can be used to test if a symmetric matrix A is positive definite:

  1. xT𝐴𝑥 > 0 for all non-zero real vectors x;
  2. λi > 0 for all eigenvalues λi of A;
  3. all leading principal submatrices have positive determinants;
  4. all the pivots without row exchange satisfy d > 0;
  5. there exists an invertible real matrix B such that A = BTB.

For the last condition, we can use the Cholesky Decomposition to find the matrix B. A Hermitian positive definite matrix has a factorisation A = LLH with L lower triangular, or A = RHR with R upper triangular. Owl’s chol returns the upper factor by default. Although named l in the example below, the result is upper triangular and satisfies A = lTl for this real input:

OCAML SESSION
# let a = Mat.of_array [|
       4.; 12.;-16.;
      12.; 37.;-43.;
     -16.;-43.; 98.;
     |] 3 3;;
val a : Owl.Mat.mat =

    C0  C1  C2
R0   4  12 -16
R1  12  37 -43
R2 -16 -43  98
# let l = Linalg.D.chol a;;
val l : Owl.Linalg.D.mat =

   C0 C1 C2
R0  2  6 -8
R1  0  1  5
R2  0  0  3
# Mat.(dot (transpose l) l =~ a);;
- : bool = true

If we know that A in 𝐴𝑥 = b is Hermitian and positive definite, we can solve RH𝑅𝑥 = b using the default upper factor, or LLHx = b when requesting upper:false. As we have seen previously, solving triangular systems is easy. For such matrices, Cholesky factorisation requires fewer operations than general LU factorisation. In Linalg, is_posdef checks whether Cholesky factorisation succeeds. The input must already be known to be symmetric or Hermitian: the routine uses one triangle and does not independently check symmetry.

OCAML SESSION
# Linalg.D.is_posdef a;;
- : bool = true

The definition of positive semidefinite is similar: A is real symmetric and xT𝐴𝑥 ≥ 0 for all real vectors x. The following Eq. 4.17 exists in many engineering analyses.

𝐴𝑥 = 𝜆𝑀𝑥 (4.17)

If A and M are real symmetric positive definite, the generalised eigenvalues λ are positive. Eigenvalues also appear in the study of the continuous-time linear system x′ = 𝐴𝑥, where

x = [x1,x2,…,xn]T (4.18) x′ = [dx1 𝑑𝑡 , dx2 𝑑𝑡 ,…, dxn 𝑑𝑡 ]T. (4.19)

We will see how to compute a Jacobian matrix in Chap. 8. In a system linearised about an equilibrium, A is the Jacobian evaluated there. For the linear system x′ = 𝐴𝑥, asymptotic stability requires all eigenvalues of A to have strictly negative real parts; positive eigenvalues instead imply growth. A symmetric positive definite matrix V for which − (V A + ATV ) is positive semidefinite guarantees Lyapunov stability. If − (V A + ATV ) is positive definite, it guarantees asymptotic stability [13].

4.6.2 Singular Value Decomposition

The singular value decomposition (SVD) is one of the most important matrix factorisations. It provides a numerically stable matrix decomposition that is both useful for many purposes and guaranteed to exist [8]. Specifically, any real m × n matrix can be factorised as:

A = UΣV T (4.20)

Here U is an m × m orthogonal matrix whose columns are eigenvectors of AAT. Similarly, V is an n × n orthogonal matrix whose columns are eigenvectors of ATA. If A has rank r, the rectangular diagonal matrix Σ has r positive singular values, the square roots of the non-zero eigenvalues of AAT and ATA; its remaining diagonal entries are zero. SVD is thus related to the eigendecompositions of these positive semidefinite matrices. For a real symmetric positive definite matrix A, the eigendecomposition QΛQT also gives an SVD.

Looking more closely, Eq. 4.20 can be expressed as Eq. 4.21. Here 𝐮𝐢 and 𝐯𝐢 are column vectors of length m and n respectively. Each 𝐮𝐢𝐯𝐢T is an m × n rank-one matrix. Therefore, SVD expresses A as a sum of r such matrices, each scaled by its singular value, ordered σ1 ≥⋯ ≥ σr > 0. The larger the singular value is, the more weight is given to its corresponding matrix. If a singular value σi is small, omitting that term introduces an error of magnitude σi in the induced 2-norm. This is a fundamental use of SVD: it can locate the “significant” components in a matrix, and is thus often used to reduce the dimension of given data.

A = [𝐮1,𝐮2,…,𝐮𝐦] [ σ1 0 … 0 0 … 0 0 σ2 … 0 0 … 0 ⋮ ⋮ … ⋮ ⋮ ⋮ ⋮ 0 0 … σr 0 … 0 ⋮ ⋮ … ⋮ ⋮ ⋮ ⋮ 0 0 … 0 0 … 0 ] [ 𝐯1T 𝐯2T ⋮ 𝐯𝐧T ] = ∑ i=1rσ i𝐮𝐢𝐯𝐢T (4.21)

Figure
(a) original

Figure
(b) n=10

Figure
(c) n=20

Figure
(d) n=50
Figure 4.1: Reconstructing an image using the leading singular components: original (a), rank-10 (b), rank-20 (c), and rank-50 (d) approximations.

As an example, we will now demonstrate how to use SVD to re-encode an image using less information, i.e. image compression. We will use

a cat image as shown in Fig. 4.1a. First, we load the image as a matrix using the code below.

OCAML
#use "imageUtils.ml";;
module N = Dense.Ndarray.S;;
module M = Dense.Matrix.S;;
let img_arr = load_ppm "cat_bw.ppm" |> N.get_slice [[];[];[0]];;
let shp = N.shape img_arr;;
let h, w = shp.(0), shp.(1);;
let img = N.reshape img_arr [|h; w|];;

The output img is a 350 × 350 matrix of floating-point values initially representing integer pixel intensities between 0 and 255 in this greyscale image. For simplicity, we don’t use external image libraries, but use the image-related utility functions in imageUtils.ml provided in the code repository of this book. It provides routines to handle the PPM image format. After obtaining img, we can apply SVD to it. The SVD is supported in the Linalg module.

OCAML SESSION
# let u, s, vt = Linalg.S.svd img;;
val s : Owl.Linalg.S.mat =

        C0      C1      C2         C347     C348     C349
R0 43899.6 7480.73 4876.87 ... 0.960703 0.694049 0.324325

The output is three matrices representing U, the singular values, and V T; only the singular-value vector is displayed above. Both u and vt are 350 × 350 matrices. The diagonal entries of Σ are returned in the row vector s, sorted from large to small. We can form a square diagonal matrix using M.diagm s, where M is the Dense.Matrix.S alias used here. By default Owl returns a reduced SVD with k = min ⁡ (m,n) singular values, an m × k matrix U, and a k × n matrix V T, so this square k × k diagonal factor also works for rectangular inputs.

Next we reconstruct the image using the first n singular values. For example, let’s set n = 10, a relatively small value. That means we need to set every element in s to zero except for the first 10, which we do by using a slicing method. You may be familiar with such array manipulation techniques from systems such as NumPy. If not, don’t worry – we will explain in detail in Chap. 5.

OCAML
let l = (N.shape s).(1);;
let n = 10;;
let s' = N.copy s;;
let z = N.zeros [|1; l - n|];;
let _ = N.set_slice [[];[n; l - 1]] s' z;;

The new Σ diagonal values are contained in s’. We can now reconstruct the original image matrix by calculating UΣ′ V T:

OCAML
let img' = M.(dot (dot u (diagm s')) vt);;

The resulting matrix img’ can be saved in PPM format using our customised image save routine in imageUtils.ml.

OCAML
let image = N.stack ~axis:2 [|img'; img'; img'|];;
let image = N.expand image 4;;
let fname = "cat_" ^ (string_of_int n) ^ ".ppm";;
let _ = save_ppm_from_arr image fname;;

The reconstructed figure is shown in Fig. 4.1b. Even though it has lost a lot of detail, it nonetheless provides a sketch of the original image. For the original matrix, we need to store 350 × 350 = 122500 values. Using SVD, each ui and vi contains 350 elements, while σi is a scalar. To reconstruct the approximation we only need to keep the first 10 ui, σi, and vi, storing 10 × (1 + 350 + 350) = 7010 values, about 5.7% of the original value count. This compares numbers of values, not bytes: the original pixels and floating-point factors use different storage formats.

While retaining far fewer values, the reconstructed image is clearly of quite low quality. We can improve it by keeping more singular values, setting n = 20 (Fig. 4.1c) and n = 50 (Fig. 4.1d). By the time we use 50 components, requiring about 28.6% of the original value count, the reconstructed figure is already quite close to the original.

Besides svd, the Linalg module also provides several variants such as svdvals returning the singular values, and gsvd performing a generalised SVD where gsvd x y -> (u, v, q, d1, d2, r) computes the generalised SVD of a pair of general rectangular matrices x and y. Here d1 and d2 contain the generalised singular value pairs of x and y. The shape of x is m × n and the shape of y is p × n.

SVD has a wide and growing range of applications [9] [10]. The example above uses a low-rank image representation, demonstrating its application in dimensionality reduction. The reconstructed image still has 350 × 350 pixels, but is represented using only 10, 20, or 50 singular components. Similarly, SVD can compress other high-dimensional data to simplify processing. In Chap. 13 we will see how truncated SVD reduces the dimension of a document-term representation in language processing; PCA uses SVD of centred data. The Moore-Penrose pseudo-inverse, which also applies to non-invertible and rectangular matrices, can be computed using SVD, and Owl provides Linalg.D.pinv for this [11].

4.7 Sparse Matrices

What we have discussed so far is based on dense matrices. But often non-zero elements are sparsely distributed, as in the identity matrix. A sparse structure can save storage and computation by avoiding explicit zero elements. The Sparse.Matrix interface described in the first edition is not exported by the Owl version in the reference environment. In this final section, we introduce sparse storage formats without assuming that interface is available.

The most intuitive method to represent a matrix is the (row, column, value) triplet where, using zero-based indices as in Owl, (1,2,10) means that the element in the second row and third column is 10. Tuples can be sorted according to row and column values to improve access efficiency.

Another commonly used format is the Compressed Sparse Row (CSR) format which is similar to the triplet above but compresses row indices. For example, suppose we must represent the following matrix:

[ 10 0 9 8 0 7 0 0 6 5 0 0 ]

The CSR format retains the column indices and values but replaces repeated row indices with row pointers. The triplets on the right of Fig. 4.2 store six row indices. The left shows the three row starts 0,3,4; a complete CSR row-pointer array also includes the terminal offset 6, giving [0,3,4,6]. Each row uses the segment between two successive pointers in the value and column-index arrays. Entries in a row need not share a column index.

Figure 4.2: Triplet representation and CSR row starts; the terminal pointer 6
is omitted from the diagram.
Figure 4.2: Triplet representation and CSR row starts; the terminal pointer 6 is omitted from the diagram.

Using this representation, one can quickly locate a given element in the sparse matrix. For example, to search the (2, 1, 5) triplet, we know that we can search this element from the index 4 by checking the compressed row indices, and then look for the column number 1. The benefit of CSR is that it is more efficient at accessing row-vectors and performing row operations. Another data structure Compressed Sparse Column (CSC) is similar but compresses column vectors instead of rows.

Triplets are an intuitive format for constructing a sparse matrix: new entries can be appended before sorting and combining duplicates. CSR and CSC provide efficient row and column access respectively, as well as arithmetic such as matrix-vector multiplication. Changing the sparsity pattern can be expensive, though updating an existing stored value need not be. Eigen, an optimised C++ library for linear algebra, implements variants of these storage schemes 1.

4.8 Summary

This chapter gave an overview of several important topics of Linear Algebra. Starting from basic vector and matrix operations, we briefly introduced several key ideas from this field, including Gaussian elimination, vector spaces, determinants, Eigenvalues, Positive Definite Matrices, etc. We demonstrated these topics with examples and code using Owl. We closed with a discussion of the sparse matrix and its representation formats used.

Bibliography

[1]
Oliphant TE. Python for scientific computing. Computing in science & engineering. 2007 Jun 18;9(3):10-20.
[2]
Baboulin M, Buttari A, Dongarra J, Kurzak J, Langou J, Langou J, Luszczek P, Tomov S. Accelerating scientific computations with mixed precision algorithms. Computer Physics Communications. 2009 Dec 1; 180(12):2526-33.
[3]
Skeel RD. Iterative refinement implies numerical stability for Gaussian elimination. Mathematics of computation. 1980; 35(151):817-32.
[4]
Zames G. Feedback and optimal sensitivity: Model reference transformations, multiplicative seminorms, and approximate inverses. IEEE Transactions on automatic control. 1981 Apr; 26(2):301-20.
[5]
Lorber A. Error propagation and figures of merit for quantification by solving matrix equations. Analytical Chemistry. 1986 May 1; 58(6):1167-72.
[6]
MacDonald JKL. Successive approximations by the Rayleigh-Ritz variation method. Physical Review. 1933 May 15; 43(10):830.
[7]
Fox RL, Kapoor MP. Rates of change of eigenvalues and eigenvectors. AIAA journal. 1968 Dec; 6(12):2426-9.
[8]
Stewart GW. On the early history of the singular value decomposition. SIAM review. 1993 Dec; 35(4):551-66.
[9]
Andrews H, Patterson C. Singular value decompositions and digital image processing. IEEE Transactions on Acoustics, Speech, and Signal Processing. 1976 Feb; 24(1):26-53.
[10]
Maciejewski AA, Klein CA. The singular value decomposition: Computation and applications to robotics. The International journal of robotics research. 1989 Dec; 8(6):63-79.
[11]
Biglieri E, Yao K. Some properties of singular value decomposition and their applications to digital signal processing. Signal Processing. 1989 Nov 1; 18(3):277-89.
[12]
Strang G. Linear Algebra and Its Applications. 3rd ed. San Diego: Harcourt Brace Jovanovich; 1988.
[13]
Cross GW. Three types of matrix stability. Linear algebra and its applications. 1978 Jun 1; 20(3):253-63.
Text from OCaml Scientific Computing by Liang Wang, Jianxin Zhao and Richard Mortier. Code: springer-book-code.