The Kitchin Research Group

If the built in linear algebra functions in numpy and scipy do not meet your needs, it is often possible to directly call lapack functions. Here we call a function to solve a set of complex linear equations. The lapack function for this is ZGBSV. The description of this function (http://linux.die.net/man/l/zgbsv) is:

ZGBSV computes the solution to a complex system of linear equations A * X = B, where A is a band matrix of order N with KL subdiagonals and KU superdiagonals, and X and B are N-by-NRHS matrices. The LU decomposition with partial pivoting and row interchanges is used to factor A as A = L * U, where L is a product of permutation and unit lower triangular matrices with KL subdiagonals, and U is upper triangular with KL+KU superdiagonals. The factored form of A is then used to solve the system of equations A * X = B.

The python signature is (http://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.lapack.zgbsv.html#scipy.linalg.lapack.zgbsv):

lub,piv,x,info = zgbsv(kl,ku,ab,b,[overwrite_ab,overwrite_b])

We will look at an example from http://www.nag.com/lapack-ex/node22.html.

We solve \(A x = b\) with

\( A = \left(

\right) \)

\( b = \left(

\right). \)

The \(A\) matrix has one lower diagonal (kl = 1) and two upper diagonals (ku = 2), four equations (n = 4) and one right-hand side.

import scipy.linalg.lapack as la

# http://www.nag.com/lapack-ex/node22.html
import numpy as np
A = np.array([[-1.65 + 2.26j, -2.05 - 0.85j,  0.97 - 2.84j,  0.0         ],
              [6.30j,         -1.48 - 1.75j, -3.99 + 4.01j,  0.59 - 0.48j],
              [0.0,           -0.77 + 2.83j, -1.06 + 1.94j,  3.33 - 1.04j],
              [0.0,            0.0,           4.48 - 1.09j, -0.46 - 1.72j]])

# construction of Ab is tricky.  Fortran indexing starts at 1, not
# 0. This code is based on the definition of Ab at
# http://linux.die.net/man/l/zgbsv. First, we create the Fortran
# indices based on the loops, and then subtract one from them to index
# the numpy arrays.
Ab = np.zeros((5,4),dtype=np.complex)
n, kl, ku = 4, 1, 2

for j in range(1, n + 1):
    for i in range(max(1, j - ku), min(n, j + kl) + 1):
        Ab[kl + ku + 1 + i - j - 1, j - 1] = A[i-1, j-1]

b = np.array([[-1.06  + 21.50j],
              [-22.72 - 53.90j],
              [28.24 - 38.60j],
              [-34.56 + 16.73j]])

lub, piv, x, info = la.flapack.zgbsv(kl, ku, Ab, b)

# compare to results at http://www.nag.com/lapack-ex/examples/results/zgbsv-ex.r
print 'x = ',x
print 'info = ',info

# check solution
print 'solved: ',np.all(np.dot(A,x) - b < 1e-12)

# here is the easy way!!!
print '\n\nbuilt-in solver'
print np.linalg.solve(A,b)

x =  [[-3.+2.j]
 [ 1.-7.j]
 [-5.+4.j]
 [ 6.-8.j]]
info =  0
solved:  True


built-in solver
[[-3.+2.j]
 [ 1.-7.j]
 [-5.+4.j]
 [ 6.-8.j]]

Some points of discussion.

1. Kind of painful! but, nevertheless, possible. You have to do a lot more work figuring out the dimensions of the problem, how to setup the problem, keeping track of indices, etc…

But, one day it might be helpful to know this can be done, e.g. to debug an installation, to validate an approach against known results, etc…

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

There are a few properties of a matrix that can make it easy to compute determinants.

1. The determinant of a triangular matrix is the product of the elements on the diagonal.
2. The determinant of a permutation matrix is (-1)**n where n is the number of permutations. Recall a permutation matrix is a matrix with a one in each row, and column, and zeros everywhere else.
3. The determinant of a product of matrices is equal to the product of the determinant of the matrices.

The LU decomposition computes three matrices such that \(A = P L U\). Thus, \(\det A = \det P \det L \det U\). \(L\) and \(U\) are triangular, so we just need to compute the product of the diagonals. \(P\) is not triangular, but if the elements of the diagonal are not 1, they will be zero, and then there has been a swap. So we simply subtract the sum of the diagonal from the length of the diagonal and then subtract 1 to get the number of swaps.

import numpy as np
from scipy.linalg import lu

A = np.array([[6, 2, 3],
              [1, 1, 1],
              [0, 4, 9]])

P, L, U = lu(A)

nswaps = len(np.diag(P)) - np.sum(np.diag(P)) - 1

detP = (-1)**nswaps
detL =  np.prod(np.diag(L)) 
detU = np.prod(np.diag(U))

print detP * detL * detU

print np.linalg.det(A)

24.0
24.0

According to the numpy documentation, a method similar to this is used to compute the determinant.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

Numpy has some gotcha features for linear algebra purists. The first is that a 1d array is neither a row, nor a column vector. That is, \(a\) = \(a^T\) if \(a\) is a 1d array. That means you can take the dot product of \(a\) with itself, without transposing the second argument. This would not be allowed in Matlab.

import numpy as np

a = np.array([0, 1, 2])
print a.shape
print a
print a.T

print
print np.dot(a, a)
print np.dot(a, a.T)

>>> >>> (3L,)
[0 1 2]
[0 1 2]
>>>
5
5

Compare the previous behavior with this 2d array. In this case, you cannot take the dot product of \(b\) with itself, because the dimensions are incompatible. You must transpose the second argument to make it dimensionally consistent. Also, the result of the dot product is not a simple scalar, but a 1 × 1 array.

b = np.array([[0, 1, 2]])
print b.shape
print b
print b.T

print np.dot(b, b)    # this is not ok, the dimensions are wrong.
print np.dot(b, b.T)
print np.dot(b, b.T).shape

(1L, 3L)
[[0 1 2]]
[[0]
 [1]
 [2]]
>>> Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: objects are not aligned
[[5]]
(1L, 1L)

Try to figure this one out! x is a column vector, and y is a 1d vector. Just by adding them you get a 2d array.

x = np.array([[2], [4], [6], [8]])
y = np.array([1, 1, 1, 1, 1, 2])
print x + y

>>> [[ 3  3  3  3  3  4]
 [ 5  5  5  5  5  6]
 [ 7  7  7  7  7  8]
 [ 9  9  9  9  9 10]]

Or this crazy alternative way to do the same thing.

x = np.array([2, 4, 6, 8])
y = np.array([1, 1, 1, 1, 1, 1, 2])

print x[:, np.newaxis] + y

>>> >>> [[ 3  3  3  3  3  3  4]
 [ 5  5  5  5  5  5  6]
 [ 7  7  7  7  7  7  8]
 [ 9  9  9  9  9  9 10]]

In the next example, we have a 3 element vector and a 4 element vector. We convert \(b\) to a 2D array with np.newaxis, and compute the outer product of the two arrays. The result is a 4 × 3 array.

a = np.array([1, 2, 3])
b = np.array([10, 20, 30, 40])

print a * b[:, np.newaxis]

>>> >>> [[ 10  40  90]
 [ 20  80 180]
 [ 30 120 270]
 [ 40 160 360]]

These concepts are known in numpy as array broadcasting. See http://www.scipy.org/EricsBroadcastingDoc and http://docs.scipy.org/doc/numpy/user/basics.broadcasting.html for more details.

These are points to keep in mind, as the operations do not strictly follow the conventions of linear algebra, and may be confusing at times.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

Matlab post Occasionally we have a set of vectors and we need to determine whether the vectors are linearly independent of each other. This may be necessary to determine if the vectors form a basis, or to determine how many independent equations there are, or to determine how many independent reactions there are.

Reference: Kreysig, Advanced Engineering Mathematics, sec. 7.4

Matlab provides a rank command which gives you the number of singular values greater than some tolerance. The numpy.rank function, unfortunately, does not do that. It returns the number of dimensions in the array. We will just compute the rank from singular value decomposition.

The default tolerance used in Matlab is max(size(A))*eps(norm(A)). Let us break that down. eps(norm(A)) is the positive distance from abs(X) to the next larger in magnitude floating point number of the same precision as X. Basically, the smallest significant number. We multiply that by the size of A, and take the largest number. We have to use some judgment in what the tolerance is, and what “zero” means.

import numpy as np
v1 = [6, 0, 3, 1, 4, 2];
v2 = [0, -1, 2, 7, 0, 5];
v3 = [12, 3, 0, -19, 8, -11];

A = np.row_stack([v1, v2, v3])

# matlab definition
eps = np.finfo(np.linalg.norm(A).dtype).eps
TOLERANCE = max(eps * np.array(A.shape))

U, s, V = np.linalg.svd(A)
print s
print np.sum(s > TOLERANCE)

TOLERANCE = 1e-14
print np.sum(s > TOLERANCE)

>>> >>> >>> >>> >>> >>> ... >>> >>> >>> >>> [  2.75209239e+01   9.30584482e+00   1.42425400e-15]
3
>>> >>> 2

You can see if you choose too small a TOLERANCE, nothing looks like zero. the result with TOLERANCE=1e-14 suggests the rows are not linearly independent. Let us show that one row can be expressed as a linear combination of the other rows.

The number of rows is greater than the rank, so these vectors are not independent. Let's demonstrate that one vector can be defined as a linear combination of the other two vectors. Mathematically we represent this as:

\(x_1 \mathit{v1} + x_2 \mathit{v2} = v3\)

or

\([x_1 x_2][v1; v2] = v3\)

This is not the usual linear algebra form of Ax = b. To get there, we transpose each side of the equation to get:

[v1.T v2.T][x_1; x_2] = v3.T

which is the form Ax = b. We solve it in a least-squares sense.

A = np.column_stack([v1, v2])
x = np.linalg.lstsq(A, v3)
print x[0]

>>> [ 2. -3.]

This shows that v3 = 2*v1 - 3*v2

#Problem set 7.4 #17
import numpy as np

v1 = [0.2, 1.2, 5.3, 2.8, 1.6]
v2 = [4.3, 3.4, 0.9, 2.0, -4.3]

A = np.row_stack([v1, v2])
U, s, V = np.linalg.svd(A)
print s

[ 7.57773162  5.99149259]

import numpy as np

A = [[1, 2, 3],
     [0, 2, 3],
     [0, 0, 1e-6]]

U, s, V = np.linalg.svd(A)
print s
print np.sum(np.abs(s) > 1e-15)
print np.sum(np.abs(s) > 1e-5)

[  5.14874857e+00   7.00277208e-01   5.54700196e-07]
3
2

import numpy as np

#    [H2  H Br2 Br HBr]
M = [[-1,  0, -1,  0,  2],  # H2 + Br2 == 2HBR
     [ 0,  0, -1,  2,  0],  # Br2 == 2Br
     [-1,  1,  0, -1,  1],  # Br + H2 == HBr + H
     [ 0, -1, -1,  1,  1],  # H + Br2 == HBr + Br
     [ 1, -1,  0,  1,  -1], # H + HBr == H2 + Br
     [ 0,  0,  1, -2,  0]]  # 2Br == Br2

U, s, V = np.linalg.svd(M)
print s
print np.sum(np.abs(s) > 1e-15)

import sympy 
M = sympy.Matrix(M)
reduced_form, inds = M.rref()

print reduced_form

labels = ['H2',  'H', 'Br2', 'Br', 'HBr']
for row in reduced_form.tolist():
    s = '0 = '
    for nu,species in zip(row,labels):
        if nu != 0:
            
            s += ' {0:+d}{1}'.format(int(nu), species)
    if s != '0 = ': print s

[  3.84742803e+00   3.32555975e+00   1.46217301e+00   1.73313660e-16
   8.57422679e-17]
3
[1, 0, 0,  2, -2]
[0, 1, 0,  1, -1]
[0, 0, 1, -2,  0]
[0, 0, 0,  0,  0]
[0, 0, 0,  0,  0]
[0, 0, 0,  0,  0]
0 =  +1H2 +2Br -2HBr
0 =  +1H +1Br -1HBr
0 =  +1Br2 -2Br

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

Given these equations, find [x1, x2, x3]

reference: Kreysig, Advanced Engineering Mathematics, 9th ed. Sec. 7.3

When solving linear equations, we can represent them in matrix form. The we simply use numpy.linalg.solve to get the solution.

import numpy as np
A = np.array([[1, -1, 1],
              [0, 10, 25],
              [20, 10, 0]])

b = np.array([0, 90, 80])

x = np.linalg.solve(A, b)
print x
print np.dot(A,x)

# Let us confirm the solution.
# this shows one element is not equal because of float tolerance
print np.dot(A,x) == b

# here we use a tolerance comparison to show the differences is less
# than a defined tolerance.
TOLERANCE = 1e-12
print np.abs((np.dot(A, x) - b)) <= TOLERANCE

[ 2.  4.  2.]
[  2.66453526e-15   9.00000000e+01   8.00000000e+01]
[False  True  True]
[ True  True  True]

It can be useful to confirm there should be a solution, e.g. that the equations are all independent. The matrix rank will tell us that. Note that numpy:rank does not give you the matrix rank, but rather the number of dimensions of the array. We compute the rank by computing the number of singular values of the matrix that are greater than zero, within a prescribed tolerance. We use the numpy.linalg.svd function for that. In Matlab you would use the rref command to see if there are any rows that are all zero, but this command does not exist in numpy. That command does not have practical use in numerical linear algebra and has not been implemented.

import numpy as np
A = np.array([[1, -1, 1],
              [0, 10, 25],
              [20, 10, 0]])

b = np.array([0, 90, 80])

# determine number of independent rows in A we get the singular values
# and count the number greater than 0.
TOLERANCE = 1e-12
u, s, v = np.linalg.svd(A)
print 'Singular values: {0}'.format(s)
print '# of independent rows: {0}'.format(np.sum(np.abs(s) > TOLERANCE))

# to illustrate a case where there are only 2 independent rows
# consider this case where row3 = 2*row2.
A = np.array([[1, -1, 1],
              [0, 10, 25],
              [0, 20, 50]])

u, s, v = np.linalg.svd(A)

print 'Singular values: {0}'.format(s)
print '# of independent rows: {0}'.format(np.sum(np.abs(s) > TOLERANCE))

Singular values: [ 27.63016717  21.49453733   1.5996022 ]
# of independent rows: 3
Singular values: [ 60.21055203   1.63994657  -0.        ]
# of independent rows: 2

Matlab comparison

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source