Fast Matrix Multiplication and Linear Solver on MicroPython

This is not a library for general matrix manipulation. As the title suggests, it does two things only:

• Multiply a matrix
• Solve a system of linear equations

Because of this single-mindedness, it is very fast compared to other MicroPython matrix libraries. Skip to the end to see the performance difference.

Multiply a matrix

\left(\begin{matrix}
  1 & 0 & 3 \\
  2 & 1 & 0 \\
  1 & 1 & 2
\end{matrix}\right)

\left(\begin{matrix}
  1 \\
  2 \\
  3
\end{matrix}\right)

= {?}

import mtx

A = [[1, 0, 3],
     [2, 1, 0],
     [1, 1, 2]]

x = [1, 2, 3]

b = mtx.mul(A, x)  # [10, 4, 9]

If you have a bunch of data points and want to matrix-multiply in batches, the convention of linear algebra is to arrange them as column vectors to form a matrix:

\left(\begin{matrix}
  1 & 0 & 3 \\
  2 & 1 & 0 \\
  1 & 1 & 2
\end{matrix}\right)

\left(\begin{matrix}
  1 & 4 \\
  2 & 0 \\
  3 & 1
\end{matrix}\right)

= {?}

This library deviates from that convention. You just have to put data points into a list, then use list comprehension:

X = [[1, 2, 3],
     [4, 0, 1]]

B = [mtx.mul(A, x) for x in X]  # [[10, 4, 9], [7, 8, 6]]

The data points look like row vectors in a matrix. That look is misleading. This library only takes a vector and multiply with a matrix. It does not multiply a matrix with a matrix.

Solve a system of linear equations

Sometimes, you know the right side of the equation, but have to find the vector in the middle:

\left(\begin{matrix}
  1 & 0 & 3 \\
  2 & 1 & 0 \\
  1 & 1 & 2
\end{matrix}\right)

\left(\begin{matrix}
  {?} \\
  {?} \\
  {?}
\end{matrix}\right)

=

\left(\begin{matrix}
  10 \\
  4  \\
  9
\end{matrix}\right)

You may try to find the inverse of that matrix, but a more efficient method is to solve the system with LU factorization:

import mtx

A = [[1, 0, 3],
     [2, 1, 0],
     [1, 1, 2]]

b = [10, 4, 9]

A_factored = mtx.lu(A)

x = mtx.solve(A_factored, b)  # [1, 2, 3]

The function mtx.lu() transforms the matrix A into an intermediate form, so the function mtx.solve() can be performed readily.

The function mtx.lu() modifies the content of A in place. If you want to preserve A, make a copy yourself:

A_factored = mtx.lu([row[:] for row in A])  # `A` unchanged

You may also solve in batches by list comprehension:

B = [[10, 4, 9],
     [ 7, 8, 6]]

A_factored = mtx.lu(A)

X = [mtx.solve(A_factored, b) for b in B]  # [[1, 2, 3], [4, 0, 1]]

Under the hood, LU factorization is done by Gaussian elimination with partial pivoting.

Performance

There is not much choice when it comes to doing matrix and linear algebra on MicroPython. I found two alternatives:

• @jalawson's umatrix + ulinalg
• @iyassou's umatrix

Comparing this library to theirs is not exactly fair. They aim to implement general matrix operations, while I focus on doing the two most common. But that is also the point: this library is able to be much faster and consumes far less memory.

Experiments are run on OpenMV Cam H7, which has a STM32H743VI ARM Cortex M7 processor at 480 MHz on board.

Thoughts

I think people are too obsessed with imitating numpy. Such an interface is useful for manipulating, analyzing, and experimenting with data, where users are at least somewhat knowledgeable of the math involved. Embedded systems, on the other hand, are more concerned with routine application of algorithms - I use this library to do planar homography on OpenMV. I think we should keep that in mind when making any math library for MicroPython.

This library, at its current state, is not well equipped to allow more complicated algorithms (e.g. QR factorization, singular value decomposition). Those would require a more structured framework of software. And that is a topic for another day.