Linear algebra

Solve \(\boldsymbol{A} \vec{x} = \vec{b}\)

import numpy as np
a = np.random.randn(5, 5)
a

array([[ 1.29828522, -0.07545962, -0.8796512 ,  0.47423191,  1.58456625],
       [-0.74702107, -0.50367163, -0.0715324 ,  0.6009195 , -0.63343534],
       [ 0.66093726, -0.12601463, -0.50620178,  2.41973627, -0.4610883 ],
       [-0.98070444,  0.01424954, -0.69370054, -1.93150585,  0.44549004],
       [ 0.86045093, -0.86686447,  0.82555562,  0.16465396, -1.36459638]])

b = np.ones((5, 1))
b

array([[1.],
       [1.],
       [1.],
       [1.],
       [1.]])

x = np.linalg.solve(a=a, b=b)
x

array([[ 0.25017917],
       [-1.6998817 ],
       [-1.64376733],
       [-0.18502463],
       [-0.51198469]])

np.matmul(a, x)

array([[1.],
       [1.],
       [1.],
       [1.],
       [1.]])

How fast is it?

%%time
n = 1000
a = np.random.randn(n, n)
b = np.ones((n, 1))
x = np.linalg.solve(a=a, b=b)

CPU times: user 42.2 ms, sys: 3.73 ms, total: 45.9 ms
Wall time: 61.9 ms

%%time
n = 2000
a = np.random.randn(n, n)
b = np.ones((n, 1))
x = np.linalg.solve(a=a, b=b)

CPU times: user 207 ms, sys: 8.64 ms, total: 216 ms
Wall time: 216 ms

%%time
n = 4000
a = np.random.randn(n, n)
b = np.ones((n, 1))
x = np.linalg.solve(a=a, b=b)

CPU times: user 1.24 s, sys: 31.1 ms, total: 1.28 s
Wall time: 1.29 s

%%time
n = 8000
a = np.random.randn(n, n)
b = np.ones((n, 1))
x = np.linalg.solve(a=a, b=b)

CPU times: user 8.51 s, sys: 132 ms, total: 8.65 s
Wall time: 8.66 s

What if A is a spase matrix?

Hint: read https://stackoverflow.com/questions/42528238/how-to-use-a-sparse-matrix-in-numpy-linalg-solve