your comments are really interesting for me. Thanks for your time.
Well, from my experience I could say that the numerical stability of an algorithm is really hard to predict by hand. Because it's strongly dependent on the values that are used. For exemple a polynomial _expression_ is, in general, stable, except when you tried to evaluate it around one of its root (and specially around a multiple root), and sometimes roots aren't easy to know (for higher degree polynomial function for exemple).
I really agree, actually, I am developing a control where splines are present, and one issue is for sure if we are close to the knots.
Concerning the rounding-error, I'm not sure why they could negligible. On the contrary the more innacurate your sensors are, the more innacurate the calculations could be. The floating-point format (32 bits or 64) is even not relevant because it's only postpone the issue, if the calculation could diverge it will take just more time (i.e. more iterations) to diverge with a higher precision format. Also, most of the time the accuracy do not cause a direct system crash, it's more devious, as the numerical operation are executed without run-time "errors" but still the value are not necessarily the one expected. So the system could be seen as error-free, but it's not !
In my case with floating point representation, what I meant is that my sensor noises are 2 or 3 orders of magnitude over the single floating point representation, in the numerical range where I use to work. So the covariance matrix should covers the rounding errors, correct me if I am wrong. All the variables that I employ are statistical, so I do not mind where is a single point, the important thing is the distribution form (for practical purposes, it does not have to be perfect the distribution neither).
As I was saying in my last email, our tool take some range of the input variables, but it also takes account of the precision of the input, so that we could predict how a better sensor could improve the accuracy (that one of the requierment that the aeronotic industry in interested in). Typically we try to use the data given by the sensor constructor to know which range the sensor have, and how many digit calculated by the sensor are correct.
This part it is really more interesting, but maybe the terminology is different for me. Sensors are just analog devices, so they do not calculate anything. Maybe you are referencing to Navigation systems? (estimation of variables). To know how many digits are reliable it is really important, and I guess it is really interesting.
For the computational efficiency I'm totally aggree with you : it's critical. Our tool for now could not garantee a specific computational efficiency, but it's on our perspectives (one other phd student of our research team works on that aspect of the problem). For what I can say now, the output program efficiency could be slightly different (in a good or a bad way). Our transformation techniques of the code could introduce a small number of new nodes, or replace some nodes by one node with a different efficency (for exemple introduce more multiplication nodes which are slower to compute). I know that could a problem, but I think I still worth the shot. Because we still may be able to obtain an accurate And efficient version of your algorithms !
It is good to know always the trade-offs yep, speed-up or accuracy, or both! :P
For the matter of C or C++ that not a big issue, I think I could input them as well in my analyzer, I'll just have to transform just a little the input code. Or I could start directly from the simulink representation of your program. Either way is good I suppose.
I have some navigation algorithms written for Matlab for prototyping purposes, maybe they will be more useful for you.
If you're interested to know about how we evaluate the rounding errors I could send you some articles.
Sure, I will reach you at your e-mail.
As I guess this discussion could be off-topic, and for not spamming the mail-list, if no one more is interested, we can follow this discussion out of the mail-list.
Summarizing, for your purposes, I can pass you some telemetry logs with Matlab code.
Héctor.
Hector Garcia de Marina <address@hidden> a écrit :
Hi Arnault,
first of all, it is always welcome to hear new points of view :P
In my opinion, if I am not wrong, the numerical stability is not a high
issue. Maybe in a Kalman Filter, computing the covariance matrix may be an
issue if it is not a positive-definite matrix.
On the other hand, do your algorithms leads to a better computational
efficiency? As far as I know, all the paparazzi embedded SW is written in C,
and I personally have some C++ code as well.
In real-time systems, this is really an issue.
About the rounding-errors, I guess the low-cost sensors that we use
introduce higher errors (noises), making the rounding-errors negligible in
the algorithms, even in 32bits floating point.
Cheers,
Héctor.
On Wed, Oct 26, 2011 at 5:25 PM, Arnault Ioualalen <
address@hidden> wrote:
Hi,
I contact this mailing list on the advise that CheBuzz gives me on IRC, so
that I could propose to the core developpers to test the numerical accuracy
of their algorithms.
Let me explain that a little :
First I'm a phd student in Perpignan (France), my work concerns the
numerical accuracy of floating-point calculations in embedded software.
Mainly, my work is on the behalf of Airbus, and adresses the issue of
rounding error propagation.
My point is, given
- a code written in some synchronous langage used in the industry (like
LUSTRE),
- and the range of the inputs (of the sensors for example)
I can :
- calculate a safe over-approximation of the numerical error induce by the
program
- propose automatically an equivalent program, this program is
mathematically equivalent but has a better numerical accuracy (I won't enter
into detail here because it's quite technical, but we already developped a
tool call Sardana wich allow us to do it).
Ok, I hope I haven't lost you !
Remember just that each time you use floating-point arithmetics each value
has a rounding error, and these rounding errors accumulate themselves during
the whole process. Some very classical examples exist, where the
rounding-errors became so big that the calculate value has nothing in common
with the expected value.
operation" and the graphical representations of your control loops.
>From what I could understand it's very much look like my kind of test data,
so I'm gessing that (with some help) I could try to optimize, separatly,
each control loop you have (or, perhaps, even together in one big piece of
code).
My main problem is that I don't really understand what kind of value each
variables could take, and your simulink-like representation may not be
really complete.
Also, I would need some range of the inputs, or even better, a trace of a
real execution of the code with the evolution of the values at each
iteration.
If some core developpers are interested in my proposal, I can answer them
over this email : address@hidden**. Or, if he lives in
France (and more specifically in Toulouse) I can go there personnaly and
meet him in person, that's not an issue (if it's not in Toulouse I could
still arrange a trip to where he is, it's just little more time-consumming
to organize).
To finish, I'll just want to say that your project could constitute an
important example for my phd thesis and I'm really interested in working
with your team over this topic of numerical accuracy.
Thanks for your answers (I hope there will be some), and sorry for this
long email but it's never easy to make such a proposal in a few lines.
Arnault Ioualalen
Phd Student
DALI team - UPVD - LIRMM
ps: sorry for the possible orthographic errors, but it has been already a
long day.
______________________________**_________________
Paparazzi-devel mailing list
address@hidden
https://lists.nongnu.org/**mailman/listinfo/paparazzi-**devel<https://lists.nongnu.org/mailman/listinfo/paparazzi-devel>
--
Héctor
--
Ce message a été vérifié par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a été trouvé.
CRI UPVD http://www.univ-perp.fr