Eigenvectors, eigenvalues fixed point calculation in C

Question

0.00/5 (No votes)

See more:

** Edited **

I tried changing the mentioned Jacobi algorithm to fixed point using libfixmath but I am not getting right results. What did I miss??

edited Jacobi code

makefile

**************************** Fisrt post ********************************************

C newbie here. I somehow got my self in the deep and i cant find my way out. If you could help that would be awesome!

The situation: I am trying to implement an ICA algorithm in C. I did so using floating point arithmetic (double, float). Now I want this code to transform it to fixed point so I can import it on an ARM microcontroller of 32 bits (thats why i cant use double, float etc).

I have found four libraries that I think can help me:

http://sourceforge.net/projects/avrfix/files/
http://www.dsprelated.com/showcode/40.php
http://sourceforge.net/p/fixedptc/code/ci/default/tree/
libfixmath

I didnt use 1. 2. or 3. I am currently trying libfixmath because allmost all calculations are done with matrices.

My problem is when trying to find the eigenvalues and eigenvectors of a covariance matrix (positive symmetic 3x3 matrix). I searched around for libs or functions that do eigendecomposition or SVD etc. but i didnt find anything.

How to you do that sort of calculation in fixed point?? Are there any functions/libs that i didnt find out? Do I have to alter the eigen function that I have in floating-point (line by line converting to fixed point - i.e fix16_from_dbl() )?

My current eigen function (not mine of course i think it is from Numerical Recipes)

jacobi.h

****Is my first question if there is anything to correct in my question please say so... :)

** Edited **

libfixmath does Cholesky, wiki and QR decomposition.

I tried to play with maths and produce the eigenvectors or eigenvalue of a matrix with this data (data from the above functions) but I failed.

If anyone knows how to do that then problem solved.

Posted 16-Feb-15 11:46am

FranxCDO

Updated 23-Feb-15 6:33am

v4

Add a Solution

Comments

nv3 16-Feb-15 18:17pm

Your question is perfectly ok. Unfortunately, as far as I know eigenvalue computation is something you typically do in floating point arithmetic. So I don't expect that there many libraries around for that purpose, which use scaled integers. Probably you will have to rewrite the algorithm you have for scaled integers. -- Sorry for the bad news.

FranxCDO 17-Feb-15 5:09am

@nv3 Thank you for your answer I will keep that in mind as my last resort.

FranxCDO 23-Feb-15 12:34pm

I did tried (because i found nothing ready calculating eigenvalues/vectors in fixed point) but unfortunately it doesn't return right results

BacchusBeale 16-Feb-15 19:23pm

I would try out OpenCV http://docs.opencv.org/modules/gpu/doc/gpu.html
I used it for other purposes, but there are many functions relating to matrices.

FranxCDO 17-Feb-15 5:17am

As i understood from the sites below OpenCV can take fixed point values and make calculation with them. RIGHT?

For the example function below for ccEigenVV does it accepts type (CV_32FC) int 32 bits??

(even if it does, isnt the return result being wrong because CV_32FC type in OpenCV is integer only not fixed (i.e Q16.16)) --> or am i saying rubbish?

1) http://docs.opencv.org/modules/core/doc/operations_on_arrays.html#eigen
2) http://docs.opencv.org/modules/core/doc/old_basic_structures.html#cvarr
3) http://docs.opencv.org/modules/core/doc/basic_structures.html#mat

Thank you!

KarstenK 17-Feb-15 6:04am

at first you must understand what code you can use for your arm mc. May you only need to multiply. Watchout for overflows.

FranxCDO 17-Feb-15 6:09am

Can you be more specific? What do you mean by code? My arm mc doesnt have an FPU (floating point unit) so i can only use fixed point arithmetic.

When I managed to find a way to implement what i want i will watch out for overflows too :)

[no name] 17-Feb-15 15:18pm

There are a lot of articles about SVD fixed Point you will find with Google. E.g. http://www.google.ch/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0CDkQFjAD&url=http%3A%2F%2Fwww.europment.org%2Flibrary%2F2013%2Fvenice%2Fbypaper%2FESPCO%2FESPCO-08.pdf&ei=LKHjVO2LAs3gOMHNgJgD&usg=AFQjCNGkp2gzOtgfqMAC9DcW_cF1FmmvvQ[^]

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Daniel Pfeffer · Answer 1 · 2015-02-23T09:25:00

Solution 1

Translating numerically-sensitive calculations to fixed point is a recipe for trouble and hard-to-find bugs - overflows, underflows, rounding errors, and other problems that would be masked by a floating-point implementation can easily crop up. Try to avoid it if at all possible!

I've just googled the ARM information centre. It claims that the ARM C compilers come with a floating-point emulation library that may be used even on CPUs with no FPU.

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0041c/Ciheagah.html[^]

Obviously, performance will suffer, but if it is good enough for your needs - this is the simplest solution.

Posted 23-Feb-15 9:25am

Daniel Pfeffer

Comments

FranxCDO 1-Mar-15 16:00pm

but is that pragmatic? I mean when and if i import my code to the board shouldnt be written in a way that they will only be fixed point arithmetic? So making the use of an FPU emulator pointless? Or am I wrong?

Daniel Pfeffer 2-Mar-15 2:37am

The whole point of an emulator is to provide floating-point capabilities on hardware which does not posses them natively. This was a popular approach up to the '90s, when most CPUs started to have floating-point instructions on-board. There is no reason why it cannot work for you, as well.

IMO, the only reasons not to use an emulator are:
1. You do not have the additional memory required for the emulator
2. The performance of the emulator is insufficient for your needs

Only if either of these is true, should you consider writing your own fixed-point implementation. As you have discovered, writing a numerically stable fixed-point package is a non-trivial task.

FranxCDO 2-Mar-15 3:45am

Oh! Thank you Daniel! I didnt know that. Live to learn... :) I am quite new with all this so excuse my lack of knowledge.

How do I find how much additional memory is required for the FPE?
Because I guess as my target is Cortex-M0 I guess thats where my problem will be!
About the second reason I just want to run it. Performance comes second. :)

Thank you again,
(i ll accept the solution as soon as i go home and try it)

Daniel Pfeffer 2-Mar-15 4:53am

The easiest way to discover the emulator size is to compile and link the code once for floating-point (assume that you do have FP instructions), and another time for the emulator. IIRC, the emulators used for DOS programs in the '90s (x86 machines, not ARM) were on the order of a few tens of kilobytes.