Direct vs Iterative Linear Solvers for nonlinears
I would like to hear users views on the observed differences when using direct solvers vs iterative linear solvers for highly nonlinear problems in either structural or fluid dynamic problems. The more nonlinear the better!!!
I am fully aware of the well known academic differences of speed, memory, robustness and accuracy etc. But I would like to hear peoples real world experience on real world complex problems. Have there been any problems where iterative solvers were just not suitable or has a solution been ground out eventually? 
Re: Direct vs Iterative Linear Solvers for nonlin
Bill
In direct answer  absolutely! The development of our Generalized Conjugate Gradient (GCG) solver was predicated out of a failure of the conventional diffusive SOR solvers. Take a look at: www.TITANAlgorithms.com/hyperion_gcg There is a plot showing residual fall off rates comparing conventional SOR to GCG. GCG is really quite amazing, the speed boosts are around x60 to x100 comparing a conventional linear thermal conductance matrix. The boost is not nearly as high for nonlinear systems such as incorporating radiation conductors in the network but it really amazing to me that it still can be setup to work on nonlinear systems in general. The adaptation to flow networks and nonlinear systems is proprietary, but I can say that it definitely does work and is worth the effort. The GCG solver is also used in www.HarvardThermal.com TASPTD and TASStress with similar performance characteristics. If I get time I will post a picture showing a sample problem which presents the spread of Eigenvalues, showing how a pinch point in the domain creates an analogous pinch point in the solution. Of course, semidirect methods have drawbacks and can be a bit jumpy and skittish, perhaps akin to a high powered sports car. Regards, DSS www.TITANAlgorithms.com 
Re: Direct vs Iterative Linear Solvers for nonlin
Hi Bill,
I don't know much regarding comparisons between direct and iterative solvers since I have never done something like that, but I've been solving fully coupled 3D incompressible NS equations (nonsymmetric and 4 dofs per node) with inexact NewtonKrylov solvers (GMRES in my case) and the results are quite amazing. I've solved problems ranging from nonNewtonian fluids (nonlinear material) to moderate Reynolds with the same code. In all cases the solver was able to reach the desired solution/accuracy. Furthermore, in some cases I was able to start the solver with linear tolerances of 0.99  in inexact solvers the linear tolerance is adapted according to the solution proximity. We have seem that, in some cases, it's easier to start the solver with relaxed linear tolerances than with tighter ones. It seems that the relaxed steps supply some better starting point to the solver evolution. Im my opinion, the direct solvers have some potencial in nonlinear methods like secant methods since you can perform some kind of decomposition, store it and use the same decomposition to quickly find the solution of the linear steps required by the nonlinear method. Regards Renato. note: Some papers are available in http://www.nacad.ufrj.br/~rnelias/pubs_e.html 
Re: Direct vs Iterative Linear Solvers for nonlin
Dear DSS (Titan Algorithms),
Is there any chance you could lower the profile on your direct marketing activities? By all means advertise your products on the site, but I personally find the 'intheface' approach during discussions more than a little offensive. Thankfully the marketing intrusions are not also exercised by others. diaw... 
Re: Direct vs Iterative Linear Solvers for nonlin
Actually I don't think these results are that impressive  SOR is not very good anyway and the choice of nonoptimal relaxation parameter (omega=1 in the graphs) makes it even worse. At a moderately high number of grid points I would expect a suitably preconditioned BiCGstab/GCR/GMRES type solver to do better than a factor of 100 over SOR.

Re: Direct vs Iterative Linear Solvers for nonlin
I'm not having a go at the TITAN people, just wondering, but is the "Generalised Conjugate Gradient" solver they talked about anything different from an SSOR preconditioned CG method??

Re: Direct vs Iterative Linear Solvers for nonlin
Hi Darren,
No offense to be taken. While I have not programmed the method you speak of, I believe perhaps it is similar. The GC is conventional for nonsymmetric matrices and applies an SOR preconditioner (Jacobi and Unity preconditioning is also a selection in the dialog). Generally for linear thermal systems (diffusion only), the Jacobi precond. is best, requiring less grind. The SOR precond is best with flow networks. Hope this answers your question Regards DSS 
Re: Direct vs Iterative Linear Solvers for nonlin
Tom
this particular solver is designed for thermal simulations. Generally speaking, these systems do not respond very well to an optimal SOR factor (w ~ 1.7). They do in academic problems, e.g. flat plat, simple fixed BC. However, large thermal systems generally are the norm and so a comparison to w = 1.0 is not overstating the performance. I reran our classic test case to see the bench mark. SOR, w = 1.95 solves in 10 seconds, GCG SOR precond, solves in 0.15 seconds, which is about x70. I will post it on the GCG page if you so inclined to take a wack at it. Are there faster benchmarks? Sure there are, but this is always tempered against general utility, covering a wide range of thermal problems. regards DSS 
Re: Direct vs Iterative Linear Solvers for nonlin
On the subject of academic vs real fluid data:
I would be extremely interested in seeing solver comparisons for incompressible NS fluid applications, using real fluid properties (kinematic viscosity) for water (~855e9 m2/s) & air (~158.95e7 m2/s). Most of the test results I have seen are for 'academic values' which are very much larger than those I have stated. In my research, I have found that 'real' fluids often act very differently to 'academic' fluids. The water response would be an interesting case in point. diaw... 
Re: Direct vs Iterative Linear Solvers for nonlin
Well just to put my 5 cents out there...
I've found that using a fully direct solver is most efficient for the Poisson problem in my fractional step code (2D unstructured FVM). I use UMFPACK by Tim Davis to form the LU factors initially and then only have to forward/back solve the triangular factors at each step. UMFPACK does a reordering which results in much sparser LU factors (often half the fillin to conventional LU). I've found this is better than Jacobi, SSOR and ILU(0) preconditioned CG methods. Obviously if you have to form the LU factors at each step this is very inefficient, so it is only good for linear problems. 
Re: Direct vs Iterative Linear Solvers for nonlin
Diaw
per you header "On the subject of academic vs real fluid data:", I believe you misread my post. GCG is a thermal conduction solver and is not designed to turn over the advectiondiffusion operators in NS simulations. Academic in this post referred to classical diffusional problem in which it can be demonstrated that over relaxation can speed solution and that an optimal SOR factor is about 1.7. Read again for clarification. Upon further review of your post, I am a little confused. Please explain. Regards, DSS www.TITANAlgorithms.com 
Re: Direct vs Iterative Linear Solvers for nonlin
"this particular solver is designed for thermal simulations. Generally speaking, these systems do not respond very well to an optimal SOR factor (w ~ 1.7). They do in academic problems, e.g. flat plat, simple fixed BC. However, large thermal systems generally are the norm and so a comparison to w = 1.0 is not overstating the performance."
This is nonsense. For a "large" system (I've done this for hires global ocean models) the optimal SOR relaxation factor approaches 2 as the resolution and there is almost no chance of it converging with omega=1. The "academic" result is a theorem in Mathematics and is correct for all types of problem  it is a general statement about the rate of convergence of the system based upon the spectral radius of the operator. As for your test case, I haven't got time to setup my model to do your exact problem but for a Poisson equation with the same number of cells shown in your figure my BiCGstab solver using a single step SIP postconditioner requires 0.06s (23 iterations) to converge to a nondimensional rms error of 1e8 on 2.4Ghz P4. If I use a preconditioned BiCGstab(2) the iteration count goes down to 11 in 0.05s. This is unlikely to change much for your problem. 
Re: Direct vs Iterative Linear Solvers for nonlin
Bill posted: I would like to hear users views on the observed differences when using direct solvers vs iterative linear solvers for highly nonlinear problems in either structural or fluid dynamic problems. The more nonlinear the better!!!
 DSS posted: I believe you misread my post. GCG is a thermal conduction solver and is not designed to turn over the advectiondiffusion operators in NS simulations. Academic in this post referred to classical diffusional problem in which it can be demonstrated that over relaxation can speed solution and that an optimal SOR factor is about 1.7. Read again for clarification. Upon further review of your post, I am a little confused. Please explain.  diaw's reply: I believe that the OP was querying about nonlinear problems  either structural, or fluiddynamic. I replied in line with his posting. I did see your reference to thermalconduction & assumed that you had considered your solver to work in nonlinear cases as well. Apologies if I confused the issue... Diffusionbased problems are usually reasonably wellbehaved & may not present too many onerous problems during solution. Real fluids acting under convectiondiffusion, on the other hand, can present some real headaches. :) diaw... 
Re: Direct vs Iterative Linear Solvers for nonlin
Tom
per quote: As for your test case, I haven't got time to setup my model to do your exact problem but for a Poisson equation with the same number of cells shown in your figure my BiCGstab solver using a single step SIP postconditioner requires 0.06s (23 iterations) to converge to a nondimensional rms error of 1e8 on 2.4Ghz P4. If I use a preconditioned BiCGstab(2) the iteration count goes down to 11 in 0.05s. This is unlikely to change much for your problem. Well then it is pointless to post a comparison for a noncompare simulation. Please construct the simulation per the posting, then let's make a grind comparison. The CV external coupling (Robin BC) is what is pinching this problem. Make sure you impose the heat flux on the bottom as well. Second if SOR worked and had an optimal SOR for all problems, linear and nonlinear, then what would the need for semidirect methods be. Certainly the effort to program these is greater than SOR (on that I would hope we could agree). I will be happy to post models where SOR just will not work, regardless of the selection of w. So NOT(Nonsense) = Sense! Kind Regards DSS 
Re: Direct vs Iterative Linear Solvers for nonlin
The solvers in question  would they be suitable for nonlinear problems? If you are going to look at a performance shootout, then it would be very useful to perform the work on a meaningful example.
Perhaps both DSS & Tom could come up with a common example & work their numeric magic? I personally would be very interested in seeing the results. Thanks... diaw... 
Re: Direct vs Iterative Linear Solvers for nonlin
"Well then it is pointless to post a comparison for a noncompare simulation. Please construct the simulation per the posting, then let's make a grind comparison. The CV external coupling (Robin BC) is what is pinching this problem. Make sure you impose the heat flux on the bottom as well."
For such a small problem this will have little effect on a CG type solver  For the size grid you're using there is actually no need to precondition at all! "Second if SOR worked and had an optimal SOR for all problems, linear and nonlinear, then what would the need for semidirect methods be. Certainly the effort to program these is greater than SOR (on that I would hope we could agree). I will be happy to post models where SOR just will not work, regardless of the selection of w. So NOT(Nonsense) = Sense!" Some final points on this topic: (1) CG type solvers are not direct or even semidirect (whatever thats meant to mean in this context  it usually means iterative application of a direct solver) they are iterative. (2) The reason CG type solvers are used over SOR is simply that, with the corect precondioning, they nearly always converge faster than SOR with optimal parameters (which may not even converge at all). Nowhere in my earlier posts did I say anything contrary to this  what I did say was I was surprised you were only a 100 times faster. Since this factor will incraese with increasing resolution the the statement 100 times faster rather meaningless as well. (3) If you really want to "sell" your software (My BiCGstab(2) solver is only about 2030 lines of FORTRAN 90 and could be coded by anyone willing to look up the research article by van der Vorst  its online) you should compare your code with linpack/blas or the numerous free codes you can get online to show that the code is worth buying! My original point was simply that being better than SOR does not mean very much  it should be better than comparable methods over a range of resolutions. (4) you should also learn something about what you are trying to sell/what your comparisons mean. You state somewhere that the optimal SOR factor is 1.7. This is not always the case  for any problem as the resolution is increased it will approach 2. The real problem is finding the optimal parameter which depends upon the Jacobi radius which is usually unknown a priori. 
need help about implementing direct solver or CG solver for pressure poisson's equation for incompressible flow . . . algorithm, code any referance is highly appreciable, thnx in advance . . .

All times are GMT 4. The time now is 11:15. 