Matrix library for MicroPython

Discussion about programs, libraries and tools that work with MicroPython. Mostly these are provided by a third party.
Target audience: All users and developers of MicroPython.
Iyassou
Posts: 29
Joined: Sun Jun 26, 2016 9:15 am

Matrix library for MicroPython

Post by Iyassou » Fri Aug 17, 2018 8:44 am

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 :)

stijn
Posts: 338
Joined: Thu Apr 24, 2014 9:13 am

Re: Matrix library for MicroPython

Post by stijn » Fri Aug 17, 2018 9:40 am

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?

Iyassou
Posts: 29
Joined: Sun Jun 26, 2016 9:15 am

Re: Matrix library for MicroPython

Post by Iyassou » Fri Aug 17, 2018 10:52 am

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".
Last edited by Iyassou on Mon Aug 20, 2018 6:45 am, edited 1 time in total.

User avatar
pythoncoder
Posts: 3506
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: Matrix library for MicroPython

Post by pythoncoder » Sat Aug 18, 2018 7:02 am

@Iyassou An excellent contribution :D
Peter Hinch

jickster
Posts: 629
Joined: Thu Sep 07, 2017 8:57 pm

Re: Matrix library for MicroPython

Post by jickster » Sat Aug 18, 2018 8:20 pm

Iyassou wrote:Hello all.

Let me know what you think :)
Write it in C and it’ll be much faster.

Iyassou
Posts: 29
Joined: Sun Jun 26, 2016 9:15 am

Re: Matrix library for MicroPython

Post by Iyassou » Sun Aug 19, 2018 5:01 pm

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 :P

jickster
Posts: 629
Joined: Thu Sep 07, 2017 8:57 pm

Re: Matrix library for MicroPython

Post by jickster » Sun Aug 19, 2018 5:07 pm

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 :P
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.

Iyassou
Posts: 29
Joined: Sun Jun 26, 2016 9:15 am

Re: Matrix library for MicroPython

Post by Iyassou » Sun Aug 19, 2018 5:23 pm

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?

jickster
Posts: 629
Joined: Thu Sep 07, 2017 8:57 pm

Re: Matrix library for MicroPython

Post by jickster » Sun Aug 19, 2018 5:28 pm

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.

Iyassou
Posts: 29
Joined: Sun Jun 26, 2016 9:15 am

Re: Matrix library for MicroPython

Post by Iyassou » Sun Aug 19, 2018 6:14 pm

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.

Post Reply