From: P Z. <zol...@gm...> - 2009-08-09 11:59:41
Attachments:
convert-to-eigen-00.path.bz2
|
Hi, here is a patch that makes ktechlab to use Eigen for calculations, so the internal matrix implementation can be removed. Steps to use: 1. patch the source. If it fails, tell me, because I haven't tested the patch :D 2. download and extract eigen somewhere. I've used version 2.0.3. (Note: see a comment in the patch about an eigen bug -- we should use a newer version when we import eigen in ktechlab ) 3. in kdevelop, in the automake manager, add the path of the extraced eigen sources to the includes. This should be done for all subfolders... 4. compile 5. run Known problems: - the caching and changed/unchanged flags probabily don't work as they should - when inserting a reactive element in the circuit, the cpu usage will increase to 100% after a time. Probable causes are that eigen uses great precision calculation, so the circuit will never enter in steady state. Or just some caching problem... Todos: - test it :D - we'll have to define _clearly_ the algorithms and data structures used in the cirucit solving process. Currently I don't know how the A, b changed flags should work and what is the purpose of CNode and CBranch classes, how/when the iterations shoud be done, and so on... Here is the sketch of the algorithm (should be extended...): if a component is added, removed, connected, ... in the circuitdocument: split the document in circuits, by connectivity create elementset from the circuit create the matrix corresponding to the elements a step in the simulator: if the circuit contains nonlinear elements solve the cirucit by iterations in each iteration call the handler of nonlinear elements recreate the LU of the eqation matrix update nodes (why?) run logic (here -- why?) check for convergence else solve as a linear system run logic (where are the components updated?) All the above shoudl be clearly defined, an only after, starting to test/refactor the implementation |
From: Alan G. <ag...@sp...> - 2009-08-09 17:27:38
|
P Zoltan wrote: > here is a patch that makes ktechlab to use Eigen for calculations, so > the internal matrix implementation can be removed. =) > Known problems: > - the caching and changed/unchanged flags probabily don't work as they > should I think that's where your memory leak is. It tries to cache everything and runs out of memory. > - when inserting a reactive element in the circuit, the cpu usage will > increase to 100% after a time. Probable causes are that eigen uses great > precision calculation, so the circuit will never enter in steady state. > Or just some caching problem... > Todos: > - test it :D > - we'll have to define _clearly_ the algorithms and data structures > used in the cirucit solving process. Currently I don't know how the A, b > changed flags should work and what is the purpose of CNode and CBranch > classes, how/when the iterations shoud be done, and so on... When the circuit is in a steady state, it doesn't make any sense to recompute LU. (simply solve LbU = x ) or something like that. Note: the function call you make "mp_lu->rank() == 0" is equivalent to a correct version of my "validate()" function. Ie, when rank = 0, the matrix is singular/invalid/unsolvable. -- IIRC. Since I'm a dunce, I hacked together the validate() function in an attempt to detect bugs in the components as early as possible. asking "rank() == 0?" does the same thing. > Here is the sketch of the algorithm (should be extended...): > if a component is added, removed, connected, ... in the circuitdocument: > split the document in circuits, by connectivity > create elementset from the circuit > create the matrix corresponding to the elements > a step in the simulator: > if the circuit contains nonlinear elements > solve the cirucit by iterations > in each iteration > call the handler of nonlinear elements > recreate the LU of the eqation matrix > update nodes (why?) Could you point me to a class, method and line number for that so that I can explain it? > run logic (here -- why?) -- cuz you could have triggered a state change. > check for convergence > else > solve as a linear system > run logic > (where are the components updated?) -- New president: Here we go again... Chemistry.com: A total rip-off. Powers are not rights. |
From: Zoltan P. <zol...@gm...> - 2009-08-12 15:57:33
|
2009/8/9 Alan Grimes <ag...@sp...> > > P Zoltan wrote: > > here is a patch that makes ktechlab to use Eigen for calculations, so > > the internal matrix implementation can be removed. > > =) > > > Known problems: > > - the caching and changed/unchanged flags probabily don't work as they > > should > > I think that's where your memory leak is. It tries to cache everything > and runs out of memory. > Memory leak? I have of that, too? > > - when inserting a reactive element in the circuit, the cpu usage will > > increase to 100% after a time. Probable causes are that eigen uses great > > precision calculation, so the circuit will never enter in steady state. > > Or just some caching problem... > > > Todos: > > - test it :D > > - we'll have to define _clearly_ the algorithms and data structures > > used in the cirucit solving process. Currently I don't know how the A, b > > changed flags should work and what is the purpose of CNode and CBranch > > classes, how/when the iterations shoud be done, and so on... > > When the circuit is in a steady state, it doesn't make any sense to > recompute LU. (simply solve LbU = x ) or something like that. > > Note: the function call you make "mp_lu->rank() == 0" is equivalent to a > correct version of my "validate()" function. Ie, when rank = 0, the > matrix is singular/invalid/unsolvable. -- IIRC. Since I'm a dunce, I > hacked together the validate() function in an attempt to detect bugs in > the components as early as possible. asking "rank() == 0?" does the same > thing. Yes, I know. Still, that rank() call should be removed, as LU::solve() method returns false if it can't solve the equation system. That case is not addressed -- the question is what to do in that case: write a "?" for voltage level, or use the last valid state for the circuit? > > > > Here is the sketch of the algorithm (should be extended...): > > > if a component is added, removed, connected, ... in the circuitdocument: > > split the document in circuits, by connectivity > > create elementset from the circuit > > create the matrix corresponding to the elements > > > a step in the simulator: > > if the circuit contains nonlinear elements > > solve the cirucit by iterations > > in each iteration > > call the handler of nonlinear elements > > recreate the LU of the eqation matrix > > update nodes (why?) > > Could you point me to a class, method and line number for that so that I > can explain it? In not that interested in a particuar class, but in the interaction of all the classes; or just the algorithm, without any particular class/method. > > > > run logic (here -- why?) > -- cuz you could have triggered a state change. > > > check for convergence > > else > > solve as a linear system > > run logic > > > (where are the components updated?) > > |
From: Alan G. <ag...@sp...> - 2009-08-12 16:25:31
|
> Yes, I know. Still, that rank() call should be removed, as LU::solve() > method returns false if it can't solve the equation system. That case is > not addressed -- the question is what to do in that case: write a "?" > for voltage level, or use the last valid state for the circuit? Yeah, you should simply skip the LU step and solve the vector with the old LU, if the vector has changed. You should also emit debugging information because it means that there is probably something wrong with one of the components. Nb, there are some pathalogical circuits that inherently produce invalid matrices. I can send you an example. -- New president: Here we go again... Chemistry.com: A total rip-off. Powers are not rights. |
From: Zoltan P. <zol...@gm...> - 2009-08-13 08:25:55
|
ok, tuning the simulator for strange cases should be done some day. First, I'd like to create something like this for ktechlab's simulation process, so the implementation could be verified against it: http://zone.ni.com/devzone/jsp/largeImage.jsp?imagename=/cms/images/devzone/tut/5(2)-5818.jpg&language=en Probabily at the end of this week i'll come with a drawing like that, so we could discuss the details. 2009/8/12 Alan Grimes <ag...@sp...> > > Yes, I know. Still, that rank() call should be removed, as LU::solve() > > method returns false if it can't solve the equation system. That case is > > not addressed -- the question is what to do in that case: write a "?" > > for voltage level, or use the last valid state for the circuit? > > Yeah, you should simply skip the LU step and solve the vector with the > old LU, if the vector has changed. > > You should also emit debugging information because it means that there > is probably something wrong with one of the components. Nb, there are > some pathalogical circuits that inherently produce invalid matrices. I > can send you an example. > > -- > New president: Here we go again... > Chemistry.com: A total rip-off. > Powers are not rights. > > > > ------------------------------------------------------------------------------ > Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day > trial. Simplify your report design, integration and deployment - and focus > on > what you do best, core application coding. Discover what's new with > Crystal Reports now. http://p.sf.net/sfu/bobj-july > _______________________________________________ > Ktechlab-devel mailing list > Kte...@li... > https://lists.sourceforge.net/lists/listinfo/ktechlab-devel > |
From: Alan G. <ag...@sp...> - 2009-08-13 14:35:36
|
Zoltan Padrah wrote: > ok, tuning the simulator for strange cases should be done some day. > First, I'd like to create something like this for ktechlab's simulation > process, so the implementation could be verified against it: > http://zone.ni.com/devzone/jsp/largeImage.jsp?imagename=/cms/images/devzone/tut/5(2)-5818.jpg&language=en > <http://zone.ni.com/devzone/jsp/largeImage.jsp?imagename=/cms/images/devzone/tut/5(2)-5818.jpg&language=en> > Probabily at the end of this week i'll come with a drawing like that, > so we could discuss the details. That's called a flow chart, there are a set of standard symbols that should always be used on flow charts. For example, decision boxes are always drawn as diamond-shaped. -- New president: Here we go again... Chemistry.com: A total rip-off. Powers are not rights. |
From: P Z. <zol...@gm...> - 2009-08-21 18:44:14
|
On Thu, 13 Aug 2009 16:33:39 +0200, Alan Grimes <ag...@sp...> wrote: > Zoltan Padrah wrote: >> ok, tuning the simulator for strange cases should be done some day. >> First, I'd like to create something like this for ktechlab's simulation >> process, so the implementation could be verified against it: >> http://zone.ni.com/devzone/jsp/largeImage.jsp?imagename=/cms/images/devzone/tut/5(2)-5818.jpg&language=en >> <http://zone.ni.com/devzone/jsp/largeImage.jsp?imagename=/cms/images/devzone/tut/5(2)-5818.jpg&language=en> >> Probabily at the end of this week i'll come with a drawing like that, >> so we could discuss the details. > > That's called a flow chart, there are a set of standard symbols that > should always be used on flow charts. For example, decision boxes are > always drawn as diamond-shaped. > > I know flowcharts for quite some time; on the linked pictures the inner workings of a circuit simulator are shown, that's what I want to clearly define. A flowcode (let's do things with style :D) made with ktechlab, attached, shows the current operations when one step in the simulation is done. It seem to me that it's too complicated and inefficient. It can be seen that in Simulator::step() there are quite a few loops, and in each loop ElementSet::doNonLinear also makes internal iterations. That's not needed, as far I know. My goal now is to make the test circiut (also attached) to run decently, without 100% processor usage. The big question is how to do it? |
From: Alan G. <ag...@sp...> - 2009-08-21 19:57:11
|
P Zoltan wrote: > A flowcode (let's do things with style :D) made with ktechlab, > attached, shows the current operations when one step in the simulation > is done. It seem to me that it's too complicated and inefficient. It can > be seen that in Simulator::step() there are quite a few loops, and in > each loop ElementSet::doNonLinear also makes internal iterations. > That's not needed, as far I know. I had forgotten about flowcode. =P Good start, looks like a great test for the flowcode code too. =) > My goal now is to make the test circiut (also attached) to run > decently, without 100% processor usage. The big question is how to do it? The circuit runs just fine for me right now with less than 50% of a single CPU (2-way SMP machine). I'm using the old engine. Naturally, things slow down if I put in a voltage probe... (which might be a problem. probably a good target for multithreading...) -- New president: Here we go again... Chemistry.com: A total rip-off. Powers are not rights. |
From: P Z. <zol...@gm...> - 2009-08-21 20:30:49
|
On Fri, 21 Aug 2009 21:55:58 +0200, Alan Grimes <ag...@sp...> wrote: > P Zoltan wrote: >> A flowcode (let's do things with style :D) made with ktechlab, >> attached, shows the current operations when one step in the simulation >> is done. It seem to me that it's too complicated and inefficient. It can >> be seen that in Simulator::step() there are quite a few loops, and in >> each loop ElementSet::doNonLinear also makes internal iterations. >> That's not needed, as far I know. > > I had forgotten about flowcode. =P > > Good start, looks like a great test for the flowcode code too. =) > It crashes quite often ;) You said before that there are some book about modified nodal analysis (?). What is the theoretical complexiti of that algorithm? Looking at the current implementation, it seem to me that ktechlab implementation is needlessly too complex. >> My goal now is to make the test circiut (also attached) to run >> decently, without 100% processor usage. The big question is how to do >> it? > > The circuit runs just fine for me right now with less than 50% of a > single CPU (2-way SMP machine). I'm using the old engine. Naturally, > things slow down if I put in a voltage probe... (which might be a > problem. probably a good target for multithreading...) > > With the old engine it's not that interesting, maybe for comparison. With the new engine ktechlab uses one core 100% if the processor is on 800Mhz, and 60% on 1800Mhz. It would also be interesting, to make a release or just normal build, without debug information, and see how fast is that. What other people think about the patch? Is it fast enough to be included? |
From: Alan G. <ag...@sp...> - 2009-08-21 21:36:48
|
P Zoltan wrote: >> P Zoltan wrote: >>> A flowcode (let's do things with style :D) made with ktechlab, >>> attached, shows the current operations when one step in the simulation >>> is done. It seem to me that it's too complicated and inefficient. It can >>> be seen that in Simulator::step() there are quite a few loops, and in >>> each loop ElementSet::doNonLinear also makes internal iterations. >>> That's not needed, as far I know. >> I had forgotten about flowcode. =P >> Good start, looks like a great test for the flowcode code too. =) > It crashes quite often ;) =( That needs to be fixed! > You said before that there are some book about modified nodal analysis > (?). What is the theoretical complexiti of that algorithm? Looking at the > current implementation, it seem to me that ktechlab implementation is > needlessly too complex. I've been using the documentation from this project: http://qucs.sourceforge.net/ -- Actually, I had not looked at where that paper had come from before, maybe we can use parts of their software too! [[ reads site more ]]... It might actually be the case that it makes sense to merge projects... They seem to be trying to re-invent ktechlab where we have a great gui and they seem to be super-geniuses when it comes to simulation.... The PDF was handed around on the mailing list some time ago. >>> My goal now is to make the test circiut (also attached) to run >>> decently, without 100% processor usage. The big question is how to do >>> it? >> The circuit runs just fine for me right now with less than 50% of a >> single CPU (2-way SMP machine). I'm using the old engine. Naturally, >> things slow down if I put in a voltage probe... (which might be a >> problem. probably a good target for multithreading...) > With the old engine it's not that interesting, maybe for comparison. With > the new engine ktechlab uses one core 100% if the processor is on 800Mhz, > and 60% on 1800Mhz. It would also be interesting, to make a release or > just normal build, without debug information, and see how fast is that. My machine is 1.2 ghz. I care far more about bugs and essential features than speed at this point. -- New president: Here we go again... Chemistry.com: A total rip-off. Powers are not rights. |
From: P Z. <zol...@gm...> - 2009-08-21 22:00:08
|
On Fri, 21 Aug 2009 23:35:40 +0200, Alan Grimes <ag...@sp...> wrote: > P Zoltan wrote: >> You said before that there are some book about modified nodal analysis >> (?). What is the theoretical complexiti of that algorithm? Looking at >> the >> current implementation, it seem to me that ktechlab implementation is >> needlessly too complex. > > I've been using the documentation from this project: > http://qucs.sourceforge.net/ > > -- Actually, I had not looked at where that paper had come from before, > maybe we can use parts of their software too! > > [[ reads site more ]]... It might actually be the case that it makes > sense to merge projects... They seem to be trying to re-invent ktechlab > where we have a great gui and they seem to be super-geniuses when it > comes to simulation.... > > The PDF was handed around on the mailing list some time ago. > I'll look on that. Maybe there is something useful. The big difference is that we want to make interactive simulation, while they not. This is an essential difference. > > I care far more about bugs and essential features than speed at this > point. > > Having a correct, well designed algorithm sounds like an essential feature for me. |
From: P Z. <zol...@gm...> - 2009-10-12 18:11:41
|
Because the performance problems in my implementation, I'll suspend the Eigen integration. Also due SVN conflicts with trunk, I'm posting the current changes here : http://sourceforge.net/userapps/trac/zoltan_padrah/ticket/4 and reverting my local copy to svn trunk. Also see the notes in my wiki (linked there). There are a few possibilities to continue: 1. fix the current implementation; eigen can be useful for verification. 2. create an in-place LU solver. Allocating / releasing a matrix in each simulator (maybe more times / step) is highly inefficient. 3. use LU only when it's useful (only linear elements) and use other solver for the other cases (nonlinear elements, ...) I'll focus now on integrating the changes proposed by Santiago Gonzalez and bugfixing. |