MicroPython Forum (Archive)

Hello all.

About two years ago I needed a matrix library and the available option was jalawson's umatrix library. One of the operations I needed was 3x3 matrix inversion. However, as jalawson stated, the library wasn't designed to be particularly fast so 3x3 matrix inversion takes about 350 ms on a Pyboard.

I was learning both MicroPython and Python 3 then (and still now), so after many revisions I've completed a presentable version of my matrix library. So far, I've tested it on a Pyboard v1.1 and a Pyboard v1.0 lite: inverting a 3x3 matrix "at worst" (details in the README.md) takes around 1.7 ms and 2.8 ms respectively.

The library includes support for complex numbers, and useful functions like copy, transpose, round, and others.

Here it is on GitHub.

Let me know what you think

Looks neat. What exactly was the main factor in getting it to run fast? Do the functions implemented have the same names as in numpy so that theoretically simple applications could be ported?

Essentially, hardcoding the determinant and inverse functions and using local variables as often as possible to avoid referencing globals often or at least twice in the method's body. For example, certain methods require property checking before doing their job and those property checks often access global variables that will be accessed later in the method, so bounding the global to a local helped improve performance.
The determinant and inverse functions were hardcoded. It's is possible to write much shorter determinant and inverse functions that use some form of recursivity to work with matrices of all sizes, but that approach is costly both computationally and in terms of memory usage. I started by writing out the formula for getting 3x3 and 4x4 matrices. Then I bound the matrix coefficients to local variables (a, b, c, d, ...) to prevent referencing self often with __getitem__ calls and wrote the exact algebraic computation directly into the return statement. It's ugly, but it is fast.

I'm not an active numpy user, so I can't say for sure. However, I know that what numpy calls "shape" I call "size" and that unlike jalawson, I haven't implemented numpy's matrix slicing functionality, so that area will require some adaptation. It shouldn't be too hard to do while making use of the "rows" and "cols" methods, which return regular lists i.e. use regular list slicing.

Edit: umatrix v1.1 supports numpy-like matrix slicing and dropped "size" in favour of "shape".

@Iyassou An excellent contribution

Iyassou wrote:Hello all.

Let me know what you think

Write it in C and it’ll be much faster.

Thanks Peter!

Although I don't know when you would need numpy-like matrix slicing on a microcontroller, I've added the functionality on a separate flavour of umatrix called umatrix_np. This flavour also supports the shape method.

The reason why I made it its own file is because I believe it's the slightly larger file size (about 1.5kB larger) that incurred a performance penalty (fractions of a millisecond) which albeit minimal is present, and I don't want to repel cutthroat applications because of a functionality they don't use. See the README for the actual numbers and decide on which flavour you'd like.

I've also updated umatrix after noticing some __getitem__ calls in the det and inverse functions and others as well, which has managed to save a few hundredths of a millisecond. umatrix_np v1.0 already contains these changes which makes its performance on par with umatrix v1.0.

jickster wrote: ↑

Sat Aug 18, 2018 8:20 pm

Write it in C and it’ll be much faster.

Although I make sense of some C programs, I can't program in it

Iyassou wrote: ↑

Sun Aug 19, 2018 5:01 pm

jickster wrote: ↑

Sat Aug 18, 2018 8:20 pm

Write it in C and it’ll be much faster.

Although I make sense of some C programs, I can't program in it

I don't blame you. It's easier to share a `.py` than C-code.
There is another way to get more performance while remaining in MicroPython: use @micropython.viper

https://www.kickstarter.com/projects/21 ... sts/664832
http://docs.micropython.org/en/v1.9.3/p ... de-emitter

I personally have NOT played around with it but since your desire is for (1) speed and (2) not using C-code, it would seem a perfect application for you.
Plus it doesn't seem like there's much time overhead in learning it.

jickster wrote: ↑

Sun Aug 19, 2018 5:07 pm

There is another way to get more performance while remaining in MicroPython: use @micropython.viper

https://www.kickstarter.com/projects/21 ... sts/664832
http://docs.micropython.org/en/v1.9.3/p ... de-emitter

I personally have NOT played around with it but since your desire is for (1) speed and (2) not using C-code, it would seem a perfect application for you.
Plus it doesn't seem like there's much time overhead in learning it.

I'll look into this. Thanks for the resource!

When re-reading umatrix I realised that it isn't really designed for cutthroat applications in the first place (redundancy of the ones and zeros functions, most probably infrequently used is_eigenvalue and is_eigenvector methods) and that it seems a bit harsh to create a whole new flavour of umatrix for matrix slicing. After looking at the performance impact matrix slicing functionality has, I'm considering merging umatrix_np into umatrix and changing the size method to shape (I'm not really a fan of the word shape in this scenario and was hanging on to prejudice, but if it's what's preferred I am flexible ).

What are your thoughts on this?

My strength is in “lower-level” of micropython and it seems you’re asking about matrix and micropython API stuff which is not my strength so I won’t give you possibly wrong advice.

jickster wrote: ↑

Sat Aug 18, 2018 8:20 pm

Write it in C and it’ll be much faster.

Out of curiosity, what do you do with the C program once you've written it to make it work with MicroPython?
I can actually program very simple things in C but don't have the same usage experience as with Python 3 and MicroPython and if this is accessible it could be the project I need to gain proficiency in it.