Bug 111574

I second that, and was actually not so long ago looking at other implementations (labplot, qtiplot, xmgrace, etc) to see how it works. It seems most are using gsl functions, so I was considering writing a plugin for that for kst based on these examples. Now that I know how to pass strings to plugins (thanks, George), I should be able to do that. It will probably lack the interactivity you are describing, but hopefully be good enough for a start. I'll keep you informed on the progress (or lack of it !)...

A first functional implementation is now in svn (kst/plugins/fits_nonlinear/general_levenberg_marquardt/). It is now yet added to the default build, but can be tested easily with the provided hand-written Makefile. There is an example that works well (and performance seems to be good even with 100 000 points !), but I'm seeing crashes in some cases with other expressions. Help is welcome for testing !
It only supports functions with one independent variable (i.e. f(x,a,b,c,...) and not f(x,y,a,b,c,...) as I'm not really sure how to add that (and whether it is really useful ?). 

It is hard to get general non-linear fits to behave reliably - so we can accept that it sometimes won't converge to something good, but at least we should require that it never crash.

What is the status of this Nicolas?  Have you tracked down your crash cases? Is it ready for wider spread testing?

I have not worked on this for quite some time, but wider spread testing and help in debugging this is certainly welcome. I think it is quite close to working correctly. Below is an excerpt from a mail exchange I had with Ingo Berg, the author of muparser, regarding the problems I had observed. I have not investigated further since then, apart from trying the same fit with xmgrace (where it worked better :-().

> I don't see a problem with the formula: y=a*exp(-b*x)+c.
> 
> In General Variables submitted to muParser must stay valid as long as 
> the parser is used. If they dont you will see an segmentation fault 
> since muParser tries to access then when evaluating the formula. There 
> is no chance of automatically validating variable pointers for 
> muParser.
> 
> Recently I receive a mail from the author of qtiplot describing 
> problems with certain formulas. Whilst in my opinion this are problems 
> related to the M-L Algorithm based on an incorrect first choice of 
> variables I see one potential source of problem if you use the Diff 
> function of muParser.
Well, actually I have verified this and qtiplot exhibits the same behavior with y=a*exp(-b*x)+c as the kst plugin. It uses the diff method indeed, so that I will have to investigate when I find some time for that. Even if you initialize the parameters with values close to the right ones, the algorithm does not seem to converge. I will have to look at whether the diff computation is the cause of the problem of the L-M algorithm itself.
I will keep you informed...

I unfortunately don't have very much time to work on that at the moment, and I'm still seeing crashes. Below is a backtrace when trying to fit the curve created with 'kst --xe 0:100:500 --ye "sqrt(2*x)+1.4*x-0.02*x^2"':

#0  0x0135620c in _int_free () from /lib/tls/libc.so.6
#1  0x0135773b in free () from /lib/tls/libc.so.6
#2  0x007936fa in function_df () from /dk/ouvea-3510-0/users/brisset/.kde/share/apps/kst/plugins/kstfit_general_levenberg_marquardt.so
#3  0x007939e6 in function_fdf () from /dk/ouvea-3510-0/users/brisset/.kde/share/apps/kst/plugins/kstfit_general_levenberg_marquardt.so
#4  0x025591ac in set (vstate=0x8fceb30, fdf=0x49, x=0x8dd7c20, f=0x8ef0dc0, J=0x8dd8328, dx=0x8fd8bd0, scale=1) at lmset.c:14
#5  0x02559dfb in lmsder_set (vstate=0x8fceb30, fdf=0xb7ada310, x=0x8dd7c20, f=0x8ef0dc0, J=0x8dd8328, dx=0x8fd8bd0) at lmder.c:327
#6  0x0255a44f in gsl_multifit_fdfsolver_set (s=0x8fd9e60, f=0xb7ad9fe8, x=0xb7ada370) at fdfsolver.c:133
#7  0x00792896 in kstfit_general_levenberg_marquardt () from /dk/ouvea-3510-0/users/brisset/.kde/share/apps/kst/plugins/kstfit_general_levenberg_marquardt.so
#8  0x008cb57f in Plugin::call () from /ldk/0/soft/kde3.5/lib/libkstmath.so.1
#9  0x008b105b in KstPlugin::update () from /ldk/0/soft/kde3.5/lib/libkstmath.so.1
#10 0x0022be3a in KstPrimitive::update () from /ldk/0/soft/kde3.5/lib/libkst.so.1
#11 0x008908d1 in KstVCurve::update () from /ldk/0/soft/kde3.5/lib/libkstmath.so.1
#12 0x00ea4eff in UpdateThread::doUpdates () from /ldk/0/soft/kde3.5/lib/libkstapp.so.1
#13 0x00ea4830 in UpdateThread::run () from /ldk/0/soft/kde3.5/lib/libkstapp.so.1
#14 0x02cad1fa in QThreadInstance::start () from /usr/lib/qt-3.3/lib/libqt-mt.so.3
#15 0x002fe98c in start_thread () from /lib/tls/libpthread.so.0
#16 0x013b016a in clone () from /lib/tls/libc.so.6
(gdb) 

If anybody has an idea where that might come from, help is welcome! Another option would be to try another implementation of the Levenberg-Marquardt solver, since even when it does not crash there are cases where the results are not as good as xmgrace's. There is a GPL'd one at http://www.ics.forth.gr/~lourakis/levmar/ which looks quite good, but I have not had time to test it yet.

SVN commit 778244 by arwalker:

CCBUG:111574 first draft of making general non-linear fitting functional

 M  +4 -1      Makefile.am  
 M  +2 -2      common.h  
 D             general_levenberg_marquardt/Makefile  
 M  +282 -161  general_levenberg_marquardt/kstfit_general_levenberg_marquardt.cpp  
 M  +45 -39    general_levenberg_marquardt/kstfit_general_levenberg_marquardt.xml  
 D             general_levenberg_marquardt/muParser.cpp  
 D             general_levenberg_marquardt/muParser.h  
 D             general_levenberg_marquardt/muParserBase.cpp  
 D             general_levenberg_marquardt/muParserBase.h  
 D             general_levenberg_marquardt/muParserBytecode.cpp  
 D             general_levenberg_marquardt/muParserBytecode.h  
 D             general_levenberg_marquardt/muParserCallback.cpp  
 D             general_levenberg_marquardt/muParserCallback.h  
 D             general_levenberg_marquardt/muParserDef.h  
 D             general_levenberg_marquardt/muParserError.cpp  
 D             general_levenberg_marquardt/muParserError.h  
 D             general_levenberg_marquardt/muParserFixes.h  
 D             general_levenberg_marquardt/muParserStack.h  
 D             general_levenberg_marquardt/muParserToken.h  
 D             general_levenberg_marquardt/muParserTokenReader.cpp  
 D             general_levenberg_marquardt/muParserTokenReader.h  
 M  +12 -12    non_linear.h  


WebSVN link: http://websvn.kde.org/?view=rev&revision=778244

SVN commit 778262 by arwalker:

BUG:111574 add the general non-linear fitting routine to the build if muParser is present

 M  +7 -0      configure.in.in  


WebSVN link: http://websvn.kde.org/?view=rev&revision=778262

Should be included in the documentation

Has been added to the documentation