Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: Soeren D. Schulze <soeren.schulze@gm...>  20130615 12:11:58

Hi everyone, I'm a student of Industrial Mathematics at the University of Bremen. I've always liked Qucs, but I've noticed the convergence problems in transient simulation. Those are one reason why I'm currently writing my Bachelor's thesis on exactly this subject. Due to months of study of the numerical mathematics involved, I think I now have quite some understanding of what's going wrong in Qucs. Last summer, I played a bit with the source code of Qucs. This is a quick comparison of my insights in the implementation and the theoretical knowledge that I've developed in the meantime. In general, the problems that arise in circuit simulation are called "DifferentialAlgebraic Equations" (DAEs). Those are equations which look like: M dx/dt = f(t,x) with a possibly singular matrix M. Compared to Ordinary Differential Equations (ODEs) dx/dt = f(t,x), they expose some very nasty numerical behavior, and Qucs doesn't really address this. 1. First of all, M and f are never really accessible in the source code. This makes it difficult to apply different numerical methods. 2. I realize that multistep methods are very popular, but concerning DAEs, they aren't always the best choice. The problem about DAEs is the decline of the condition number of the Jacobian with small stepsize. Upon stability problems, multistep methods often require low order and small stepsize, which may be fatal in the case of circuit simulation. The "fallback" method "Implicit Euler and minimum stepsize" is about the worst thing you can do. There are equations on which the Implicit Euler method doesn't even converge in theory, and even less so in practice. To me, implicit onestep methods are far more promising because they show excellent stability even at arbitrarily high order. They're harder to implement, but good implementations have been in existence since the 1990s (most prominently radau5.f). 3. The implementation Newton's method is *very* unfortunate because it effectively factors out the Jacobian, squaring the condition of the problem. As the condition number is often bad enough anyway (see above), this can be fatal, too. It's very laudable that the Jacobian is calculated analytically (though not necessary with an otherwise good implementation), but running a new decomposition on every Newton iteration is just a waste of calculation time. 4. In the context of my Bachelor's thesis, I have developed a method which improves the condition problems, sometimes fixing them entirely. I have proven the theory about it, and now I'm just personally curious how well it performs in practice. The methods employs Singular Value Decomposition, which is already implemented in Qucs, but it applies it an a different way. Unfortunately, the general numerical approach is quite hardcoded in Qucs, which makes it nontrivial to improve anything. As a first step, (1) has to be fixed, so it will be possible at all to link Qucs to some preexisting code. I see that Qucs implements a huge number of methods on its own, but I don't really understand the reason, as there exist highly optimized implementations in Netlib and similar libraries. I'm currently still busy with my thesis and some other things, but I will have time in August and September. Is there anyone who currently maintains the backend? I'd rather communicate my changes to someone who knows the current code and who will be around for some time in the future (which I can't promise for myself once the next semester starts). Sören 
From: Mario Trangoni <mjtrangoni@gm...>  20130616 14:06:43

Hi Soeren, You are right, the core of qucs should be linked or should be offering the possibility of linking to different external math libraries like the netlibs. With them Qucs would use in a better way the new computer architectures like the dualcore, quadcore or even distributed architectures like clusters :). I did simulations with 100000 points and it has taken like 30 minutes, so I'm interested in helping you with the redesign of the qucscore. Regards, Mario Trangoni 
From: Frans Schreuder <fransschreuder@gm...>  20130616 19:11:25

Dear Sören, Thank you for your offer to help. I do indeed think that the transient simulator needs some attention. I currently don't have much knowledge about transient simulations but I am willing to learn; my main knowledge is about sparameter and frequencydomain simulations. Stefan Jahn who has written the simulator is not active in the project anymore, so the knowledge about the simulator is now a little scattered amongst the new team members of qucs. I think that we do need to make these changes in a separate branch as it may break some functionality when implementation starts. If you give me your sf username, I will add you to the developers list. Regards, Frans On 150613 14:11, Soeren D. Schulze wrote: > Hi everyone, > > I'm a student of Industrial Mathematics at the University of Bremen. > I've always liked Qucs, but I've noticed the convergence problems in > transient simulation. Those are one reason why I'm currently writing my > Bachelor's thesis on exactly this subject. Due to months of study of > the numerical mathematics involved, I think I now have quite some > understanding of what's going wrong in Qucs. > > Last summer, I played a bit with the source code of Qucs. This is a > quick comparison of my insights in the implementation and the > theoretical knowledge that I've developed in the meantime. > > In general, the problems that arise in circuit simulation are called > "DifferentialAlgebraic Equations" (DAEs). Those are equations which > look like: > > M dx/dt = f(t,x) > > with a possibly singular matrix M. > Compared to Ordinary Differential Equations (ODEs) > > dx/dt = f(t,x), > > they expose some very nasty numerical behavior, and Qucs doesn't really > address this. > > 1. First of all, M and f are never really accessible in the source code. > This makes it difficult to apply different numerical methods. > > 2. I realize that multistep methods are very popular, but concerning > DAEs, they aren't always the best choice. The problem about DAEs is the > decline of the condition number of the Jacobian with small stepsize. > Upon stability problems, multistep methods often require low order and > small stepsize, which may be fatal in the case of circuit simulation. > The "fallback" method "Implicit Euler and minimum stepsize" is about the > worst thing you can do. There are equations on which the Implicit Euler > method doesn't even converge in theory, and even less so in practice. > To me, implicit onestep methods are far more promising because they > show excellent stability even at arbitrarily high order. They're harder > to implement, but good implementations have been in existence since the > 1990s (most prominently radau5.f). > > 3. The implementation Newton's method is *very* unfortunate because it > effectively factors out the Jacobian, squaring the condition of the > problem. As the condition number is often bad enough anyway (see > above), this can be fatal, too. It's very laudable that the Jacobian is > calculated analytically (though not necessary with an otherwise good > implementation), but running a new decomposition on every Newton > iteration is just a waste of calculation time. > > 4. In the context of my Bachelor's thesis, I have developed a method > which improves the condition problems, sometimes fixing them entirely. > I have proven the theory about it, and now I'm just personally curious > how well it performs in practice. The methods employs Singular Value > Decomposition, which is already implemented in Qucs, but it applies it > an a different way. > > > Unfortunately, the general numerical approach is quite hardcoded in > Qucs, which makes it nontrivial to improve anything. As a first step, > (1) has to be fixed, so it will be possible at all to link Qucs to some > preexisting code. I see that Qucs implements a huge number of methods > on its own, but I don't really understand the reason, as there exist > highly optimized implementations in Netlib and similar libraries. > > I'm currently still busy with my thesis and some other things, but I > will have time in August and September. Is there anyone who currently > maintains the backend? I'd rather communicate my changes to someone > who knows the current code and who will be around for some time in the > future (which I can't promise for myself once the next semester starts). > > > Sören > >  > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windowsdev2dev > _______________________________________________ > Qucsdevel mailing list > Qucsdevel@... > https://lists.sourceforge.net/lists/listinfo/qucsdevel 
From: Frans Schreuder <fransschreuder@gm...>  20130616 20:40:47

Dear Sören, > > My username is "sdschulze". But don't expect any input before August. > Don't worry, we don't force you to do anything. Anyway I added you to developers. > I'm still wondering... Are you aware of any policy in Qucs that > states "don't use external libraries"? Handcoding half a dozen > different methods for LU decomposition seems a bit extreme. It's > perhaps a nice school project, but in Qucs, they just increase the > maintenance effort, whereas LAPACK already has many implementations > that are known to work well. > > I also think it is a good idea to use external libraries rather than inventing the wheel. I don't know why former developers have chosen to write all those functions themselves. I also joined qucs only a few months ago. It is important to realize though that we have an application that runs on multiple platforms. Lapack does run on Linux, windows and mac, but there may be other libraries, that are more difficult to port. Frans 
From: Bastien ROUCARIES <roucaries.bastien@gm...>  20130617 17:29:32

Le 16 juin 2013 22:40, "Frans Schreuder" <fransschreuder@...> a écrit : > > Dear Sören, > > > > My username is "sdschulze". But don't expect any input before August. > > > Don't worry, we don't force you to do anything. Anyway I added you to > developers. > > I'm still wondering... Are you aware of any policy in Qucs that > > states "don't use external libraries"? Handcoding half a dozen > > different methods for LU decomposition seems a bit extreme. It's > > perhaps a nice school project, but in Qucs, they just increase the > > maintenance effort, whereas LAPACK already has many implementations > > that are known to work well. > > > > > I also think it is a good idea to use external libraries rather than > inventing the wheel. I don't know why former developers have chosen to > write all those functions themselves. I also joined qucs only a few > months ago. > It is important to realize though that we have an application that runs > on multiple platforms. Lapack does run on Linux, windows and mac, but > there may be other libraries, that are more difficult to port SEE Aldo libeigen c++ portable and faster than Blas/lapack > > Frans > > >  > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windowsdev2dev > _______________________________________________ > Qucsdevel mailing list > Qucsdevel@... > https://lists.sourceforge.net/lists/listinfo/qucsdevel 
From: Soeren D. Schulze <soeren.schulze@gm...>  20130622 08:01:24

Am 20.06.2013 10:18, schrieb Richard Crozier: > Hi All, > > Bear in mind however, that there is in progress work to add an option to > use the gnucap solver as the Qucs simulation backend. The gnucap solver > is much faster, and also more memory efficient, being based on a sparse > matrix representation. Working to help add this option might be a faster > route to a 'better' solver algorithm than modifying the existing solver. Ah, that's interesting. Does the gnucap solver support everything that we need, so it can replace the Qucs solver, or is it just supposed to be an option? Right now, I'm only interestested in convergence, not so much in speed. But do you know if convergence is also better in gnucap? > Also I would also really be wanting to see how these changes would > impact my integration of the Qucs solvers with Octave, so if we can keep > anything related to this quite firmly on a feature branch or fork until > everyone agrees to merge anything I would really appreciate it. Yes, we should really do that. Sören 
From: Frans Schreuder <fransschreuder@gm...>  20130622 08:13:25

On 220613 10:01, Soeren D. Schulze wrote: > Am 20.06.2013 10:18, schrieb Richard Crozier: >> Hi All, >> >> Bear in mind however, that there is in progress work to add an option to >> use the gnucap solver as the Qucs simulation backend. The gnucap solver >> is much faster, and also more memory efficient, being based on a sparse >> matrix representation. Working to help add this option might be a faster >> route to a 'better' solver algorithm than modifying the existing solver. > Ah, that's interesting. Does the gnucap solver support everything that > we need, so it can replace the Qucs solver, or is it just supposed to be > an option? qucscore has some features that can not be found in gnucap, like sparameter simulations. I don't think it will replace qucscore any time soon. We could start by supporting gnucap through a transient_gnucap simulation for example. > Right now, I'm only interestested in convergence, not so much in speed. > But do you know if convergence is also better in gnucap? > >> Also I would also really be wanting to see how these changes would >> impact my integration of the Qucs solvers with Octave, so if we can keep >> anything related to this quite firmly on a feature branch or fork until >> everyone agrees to merge anything I would really appreciate it. > Yes, we should really do that. > > > Sören > >  > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windowsdev2dev > _______________________________________________ > Qucsdevel mailing list > Qucsdevel@... > https://lists.sourceforge.net/lists/listinfo/qucsdevel 
From: Richard Crozier <r.crozier@ed...>  20130622 10:29:04

"Soeren D. Schulze" <soeren.d.schulze@...> wrote: >Am 20.06.2013 10:18, schrieb Richard Crozier: >> Hi All, >> >> Bear in mind however, that there is in progress work to add an option >to >> use the gnucap solver as the Qucs simulation backend. The gnucap >solver >> is much faster, and also more memory efficient, being based on a >sparse >> matrix representation. Working to help add this option might be a >faster >> route to a 'better' solver algorithm than modifying the existing >solver. > >Ah, that's interesting. Does the gnucap solver support everything that >we need, so it can replace the Qucs solver, or is it just supposed to >be >an option? > Well, basically, the idea was/is to have gnucap as an optional backend that could be selecte somewhere in the Qucs gui. The gnucap guys talked about creating a plugin for gnucap that allowed it to work with qucs and the qucs files etc. I have to say I haven't followed development of this very closely. It is initially just supposed to be an option. >Right now, I'm only interestested in convergence, not so much in speed. > But do you know if convergence is also better in gnucap? > Actually i don't know, and it's possible it isn't, but i gather the solver is somewhat more advanced, doing full mixedmode simulation, but i don't know if it is actually also more stable or not. >> Also I would also really be wanting to see how these changes would >> impact my integration of the Qucs solvers with Octave, so if we can >keep >> anything related to this quite firmly on a feature branch or fork >until >> everyone agrees to merge anything I would really appreciate it. > >Yes, we should really do that. > > >Sören I do still think improvements are welcome, my work doesn't really touch the solvers themselves, but gets the solution between each time step, from a class which inheirits the trsolver class. I haven't pushed any of this yet though. Improving the existing solver is a worthwhile exercise though. I would also like to understand them better myself.  Sent from my phone. Please excuse my brevity. The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. 
From: Richard Crozier <r.crozier@ed...>  20130620 08:18:58

On 17/06/2013 18:29, Bastien ROUCARIES wrote: > Le 16 juin 2013 22:40, "Frans Schreuder" <fransschreuder@...> a > écrit : >> Dear Sören, >>> My username is "sdschulze". But don't expect any input before August. >>> >> Don't worry, we don't force you to do anything. Anyway I added you to >> developers. >>> I'm still wondering... Are you aware of any policy in Qucs that >>> states "don't use external libraries"? Handcoding half a dozen >>> different methods for LU decomposition seems a bit extreme. It's >>> perhaps a nice school project, but in Qucs, they just increase the >>> maintenance effort, whereas LAPACK already has many implementations >>> that are known to work well. >>> >>> >> I also think it is a good idea to use external libraries rather than >> inventing the wheel. I don't know why former developers have chosen to >> write all those functions themselves. I also joined qucs only a few >> months ago. >> It is important to realize though that we have an application that runs >> on multiple platforms. Lapack does run on Linux, windows and mac, but >> there may be other libraries, that are more difficult to port > SEE Aldo libeigen c++ portable and faster than Blas/lapack > >> Frans >> >> >> > Hi All, Bear in mind however, that there is in progress work to add an option to use the gnucap solver as the Qucs simulation backend. The gnucap solver is much faster, and also more memory efficient, being based on a sparse matrix representation. Working to help add this option might be a faster route to a 'better' solver algorithm than modifying the existing solver. Also I would also really be wanting to see how these changes would impact my integration of the Qucs solvers with Octave, so if we can keep anything related to this quite firmly on a feature branch or fork until everyone agrees to merge anything I would really appreciate it. Regards, Richard  The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. 
From: Bastien ROUCARIES <roucaries.bastien@gm...>  20130623 18:31:51

Le 20 juin 2013 10:18, "Richard Crozier" <r.crozier@...> a écrit : > > On 17/06/2013 18:29, Bastien ROUCARIES wrote: >> >> Le 16 juin 2013 22:40, "Frans Schreuder" <fransschreuder@...> a >> écrit : >>> >>> Dear Sören, >>>> >>>> My username is "sdschulze". But don't expect any input before August. >>>> >>> Don't worry, we don't force you to do anything. Anyway I added you to >>> developers. >>>> >>>> I'm still wondering... Are you aware of any policy in Qucs that >>>> states "don't use external libraries"? Handcoding half a dozen >>>> different methods for LU decomposition seems a bit extreme. It's >>>> perhaps a nice school project, but in Qucs, they just increase the >>>> maintenance effort, whereas LAPACK already has many implementations >>>> that are known to work well. >>>> >>>> >>> I also think it is a good idea to use external libraries rather than >>> inventing the wheel. I don't know why former developers have chosen to >>> write all those functions themselves. I also joined qucs only a few >>> months ago. >>> It is important to realize though that we have an application that runs >>> on multiple platforms. Lapack does run on Linux, windows and mac, but >>> there may be other libraries, that are more difficult to port >> >> SEE Aldo libeigen c++ portable and faster than Blas/lapack >> >>> Frans >>> >>> >>> >> > > Hi All, > > Bear in mind however, that there is in progress work to add an option to use the gnucap solver as the Qucs simulation backend. The gnucap solver is much faster, and also more memory efficient, being based on a sparse matrix representation. Working to help add this option might be a faster route to a 'better' solver algorithm than modifying the existing solver. I like gnucap but adding sparse matrix to qucs will be really easy when porting matrix class of qucs to libeigen. Only a matter of a few line of code. Will try to post some patch. Bastien > > Also I would also really be wanting to see how these changes would impact my integration of the Qucs solvers with Octave, so if we can keep anything related to this quite firmly on a feature branch or fork until everyone agrees to merge anything I would really appreciate it. > > Regards, > Richard > >  > The University of Edinburgh is a charitable body, registered in > Scotland, with registration number SC005336. > 
From: Soeren D. Schulze <soeren.schulze@gm...>  20130702 15:31:57

Am 20.06.2013 10:18, schrieb Richard Crozier: > > Bear in mind however, that there is in progress work to add an option to > use the gnucap solver as the Qucs simulation backend. The gnucap solver > is much faster, and also more memory efficient, being based on a sparse > matrix representation. Working to help add this option might be a faster > route to a 'better' solver algorithm than modifying the existing solver. To get it *really* fast (in case of large circuits), we should use some stateoftheart iterative linear solver, such as GMRES. That is especially appealing because the predictor provides some good guess that can be used as an initial value. But preconditioning is probably critical. Sören 
From: roucaries bastien <roucaries.bastien+<qucs@gm...>  20130703 06:53:17

On Tue, Jul 2, 2013 at 5:31 PM, Soeren D. Schulze <soeren.d.schulze@...> wrote: > Am 20.06.2013 10:18, schrieb Richard Crozier: >> >> Bear in mind however, that there is in progress work to add an option to >> use the gnucap solver as the Qucs simulation backend. The gnucap solver >> is much faster, and also more memory efficient, being based on a sparse >> matrix representation. Working to help add this option might be a faster >> route to a 'better' solver algorithm than modifying the existing solver. > > To get it *really* fast (in case of large circuits), we should use some > stateoftheart iterative linear solver, such as GMRES. That is > especially appealing because the predictor provides some good guess that > can be used as an initial value. But preconditioning is probably critical. Using KLU will be good also http://www.cise.ufl.edu/research/sparse/klu/ > > Sören > >  > This SF.net email is sponsored by Windows: > > Build for Windows Store. > > http://p.sf.net/sfu/windowsdev2dev > _______________________________________________ > Qucsdevel mailing list > Qucsdevel@... > https://lists.sourceforge.net/lists/listinfo/qucsdevel 
From: al davis <ad212@fr...>  20130704 02:44:25

On Tuesday 02 July 2013, Soeren D. Schulze wrote: > To get it really fast (in case of large circuits), we should > use some stateoftheart iterative linear solver, such as > GMRES. That is To get it really fast, you need to fine tune everything. Fast matrix eval, fast model eval, watch cache hits, which functions to inline, step control, know when you can take shortcuts, how data is stored, .... Using a packaged library solver won't get you there. About 10 years ago, there were lots of papers about "Krylov subspace methods", all quoting huge improvements over spice for some special kind of circuit. They all missed the point. I have some large benchmarks for Gnucap ... One, with 589825 nodes. Gnucap transient analysis takes about a minute with default settings. NGspice takes over 8 hours to do the same. In Gnucap, only about 20% of that time has to do with the matrix. This is a linear circuit. For a nonlinear circuit, the matrix portion would be even less percentagewise, because of more time in model evaluation. I can make it faster by changing the options to tradeoff some accuracy for speed. The numbers I stated here are for the default "spice accuracy with improved robustness". Having said all that .. I am curious how some other methods perform in this situation. The matrix solver is one file in gnucap. If you want to try another, I would really like to see the results, so I will help you do it. 
From: Soeren D. Schulze <soeren.schulze@gm...>  20130706 08:38:46

You're absolutely right. There are bottlenecks in Qucs all over the place. First of all, though, I'd like to fix the convergence problems because a fast but divergent solver isn't really worth anything. BDF methods are usually fastest (when implemented right), but they're also a bit fragile, so I think we should provide a onestep method, too. Apart from the linear solvers, the first bottleneck that caught my attention is the application of traditional Newton's method, which entails recomputation and redecomposition of the Jacobian in every step. We should really use simplified Newton's method. While the theory says that traditional Newton's method has faster convergence, trading a few extra function evaluations (at most O(n^2), probably more like O(n)) for O(n^3) operations seems like a good deal. OK, applying some better matrix methods may reduce the latter to O(n^2), but the point still holds. And if we use onestep methods, we have to use simplified Newton's method anyway. The second bottleneck seems to be the polynomial interpolation to get the coefficients for the multistep methods. It would be interesting to profile the percentage of the computation time that this actually takes. The cost is independent of the matrix size, but because it needs to be done in every step and upon every rejection, I think it's not negligible. But before changing anything here, it should be checked what welltested codes like DASSL/DASPK do. Sören Am 04.07.2013 04:31, schrieb al davis: > On Tuesday 02 July 2013, Soeren D. Schulze wrote: >> To get it really fast (in case of large circuits), we should >> use some stateoftheart iterative linear solver, such as >> GMRES. That is > > To get it really fast, you need to fine tune everything. Fast > matrix eval, fast model eval, watch cache hits, which functions > to inline, step control, know when you can take shortcuts, how > data is stored, .... > > Using a packaged library solver won't get you there. > > About 10 years ago, there were lots of papers about "Krylov > subspace methods", all quoting huge improvements over spice for > some special kind of circuit. They all missed the point. > > I have some large benchmarks for Gnucap ... One, with 589825 > nodes. Gnucap transient analysis takes about a minute with > default settings. NGspice takes over 8 hours to do the same. > > In Gnucap, only about 20% of that time has to do with the > matrix. This is a linear circuit. For a nonlinear circuit, the > matrix portion would be even less percentagewise, because of > more time in model evaluation. > > I can make it faster by changing the options to tradeoff some > accuracy for speed. The numbers I stated here are for the > default "spice accuracy with improved robustness". > > Having said all that .. I am curious how some other methods > perform in this situation. The matrix solver is one file in > gnucap. If you want to try another, I would really like to see > the results, so I will help you do it. 