From: Soeren D. S. <soe...@gm...> - 2013-06-15 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 "Differential-Algebraic 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 multi-step 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, multi-step 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 one-step 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 non-trivial to improve anything. As a first step, (1) has to be fixed, so it will be possible at all to link Qucs to some pre-existing 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 back-end? 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 T. <mjt...@gm...> - 2013-06-16 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 dual-core, quad-core 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 qucs-core. Regards, Mario Trangoni |
From: Frans S. <fra...@gm...> - 2013-06-16 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 s-parameter and frequency-domain 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 15-06-13 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 > "Differential-Algebraic 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 multi-step 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, multi-step 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 one-step 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 non-trivial to improve anything. As a first step, > (1) has to be fixed, so it will be possible at all to link Qucs to some > pre-existing 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 back-end? 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/windows-dev2dev > _______________________________________________ > Qucs-devel mailing list > Quc...@li... > https://lists.sourceforge.net/lists/listinfo/qucs-devel |
From: Frans S. <fra...@gm...> - 2013-06-16 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"? Hand-coding 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 R. <rou...@gm...> - 2013-06-17 17:29:32
|
Le 16 juin 2013 22:40, "Frans Schreuder" <fra...@gm...> 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"? Hand-coding 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/windows-dev2dev > _______________________________________________ > Qucs-devel mailing list > Quc...@li... > https://lists.sourceforge.net/lists/listinfo/qucs-devel |
From: Soeren D. S. <soe...@gm...> - 2013-06-22 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 S. <fra...@gm...> - 2013-06-22 08:13:25
|
On 22-06-13 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? qucs-core has some features that can not be found in gnucap, like s-parameter simulations. I don't think it will replace qucs-core 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/windows-dev2dev > _______________________________________________ > Qucs-devel mailing list > Quc...@li... > https://lists.sourceforge.net/lists/listinfo/qucs-devel |
From: Richard C. <r.c...@ed...> - 2013-06-22 10:29:04
|
"Soeren D. Schulze" <soe...@gm...> 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 back-end 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 mixed-mode 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 C. <r.c...@ed...> - 2013-06-20 08:18:58
|
On 17/06/2013 18:29, Bastien ROUCARIES wrote: > Le 16 juin 2013 22:40, "Frans Schreuder" <fra...@gm...> 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"? Hand-coding 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 R. <rou...@gm...> - 2013-06-23 18:31:51
|
Le 20 juin 2013 10:18, "Richard Crozier" <r.c...@ed...> a écrit : > > On 17/06/2013 18:29, Bastien ROUCARIES wrote: >> >> Le 16 juin 2013 22:40, "Frans Schreuder" <fra...@gm...> 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"? Hand-coding 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. S. <soe...@gm...> - 2013-07-02 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 state-of-the-art 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 pre-conditioning is probably critical. Sören |
From: roucaries b. <rou...@gm...> - 2013-07-03 06:53:17
|
On Tue, Jul 2, 2013 at 5:31 PM, Soeren D. Schulze <soe...@gm...> 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 > state-of-the-art 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 pre-conditioning 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/windows-dev2dev > _______________________________________________ > Qucs-devel mailing list > Quc...@li... > https://lists.sourceforge.net/lists/listinfo/qucs-devel |
From: al d. <ad...@fr...> - 2013-07-04 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 state-of-the-art 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. S. <soe...@gm...> - 2013-07-06 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 one-step 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 re-decomposition 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 one-step 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 multi-step 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 well-tested 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 state-of-the-art 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. |