CFD Online Discussion Forums (http://www.cfd-online.com/Forums/)
-   Main CFD Forum (http://www.cfd-online.com/Forums/main/)
-   -   Direct vs Iterative Linear Solvers for non-linears (http://www.cfd-online.com/Forums/main/11211-direct-vs-iterative-linear-solvers-non-linears.html)

 bill April 11, 2006 13:56

Direct vs Iterative Linear Solvers for non-linears

I would like to hear users views on the observed differences when using direct solvers vs iterative linear solvers for highly non-linear problems in either structural or fluid dynamic problems. The more non-linear 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?

 TITAN Algorithms, Staff April 11, 2006 19:48

Re: Direct vs Iterative Linear Solvers for non-lin

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 TAS-Stress 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, semi-direct methods have drawbacks and can be a bit jumpy and skittish, perhaps akin to a high powered sports car.

Regards,

DSS

www.TITANAlgorithms.com

 Renato. April 11, 2006 21:28

Re: Direct vs Iterative Linear Solvers for non-lin

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 (non-symmetric and 4 dofs per node) with inexact Newton-Krylov solvers (GMRES in my case) and the results are quite amazing. I've solved problems ranging from non-Newtonian 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

 diaw (Des Aubery) April 12, 2006 05:42

Re: Direct vs Iterative Linear Solvers for non-lin

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 'in-the-face' approach during discussions more than a little offensive.

Thankfully the marketing intrusions are not also exercised by others.

diaw...

 Tom April 12, 2006 08:42

Re: Direct vs Iterative Linear Solvers for non-lin

Actually I don't think these results are that impressive - SOR is not very good anyway and the choice of non-optimal 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.

 Darren April 12, 2006 19:13

Re: Direct vs Iterative Linear Solvers for non-lin

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??

 TITAN Algorithms, Staff April 12, 2006 20:41

Re: Direct vs Iterative Linear Solvers for non-lin

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 non-symmetric 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.

Regards

DSS

 TITAN Algorithms, Staff April 12, 2006 20:58

Re: Direct vs Iterative Linear Solvers for non-lin

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

 diaw (Des Aubery) April 12, 2006 23:56

Re: Direct vs Iterative Linear Solvers for non-lin

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 (~855e-9 m2/s) & air (~158.95e-7 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...

 Darren April 13, 2006 00:07

Re: Direct vs Iterative Linear Solvers for non-lin

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 re-ordering which results in much sparser LU factors (often half the fill-in 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.

 TITAN Algorithms, Staff April 13, 2006 05:42

Re: Direct vs Iterative Linear Solvers for non-lin

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 advection-diffusion 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

 Tom April 13, 2006 06:30

Re: Direct vs Iterative Linear Solvers for non-lin

"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 1e-8 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.

 diaw (Des Aubery) April 13, 2006 08:19

Re: Direct vs Iterative Linear Solvers for non-lin

Bill posted: I would like to hear users views on the observed differences when using direct solvers vs iterative linear solvers for highly non-linear problems in either structural or fluid dynamic problems. The more non-linear the better!!!

------------ DSS posted:

I believe you misread my post. GCG is a thermal conduction solver and is not designed to turn over the advection-diffusion 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.

I believe that the OP was querying about non-linear problems - either structural, or fluid-dynamic. I replied in line with his posting. I did see your reference to thermal-conduction & assumed that you had considered your solver to work in non-linear cases as well. Apologies if I confused the issue...

Diffusion-based problems are usually reasonably well-behaved & may not present too many onerous problems during solution. Real fluids acting under convection-diffusion, on the other hand, can present some real headaches. :)

diaw...

 TITAN Algorithms April 14, 2006 06:57

Re: Direct vs Iterative Linear Solvers for non-lin

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 1e-8 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 non-compare 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 semi-direct 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

 diaw (Des Aubery) April 14, 2006 07:45

Re: Direct vs Iterative Linear Solvers for non-lin

The solvers in question - would they be suitable for non-linear problems? If you are going to look at a performance shoot-out, 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...

 Tom April 14, 2006 15:15

Re: Direct vs Iterative Linear Solvers for non-lin

"Well then it is pointless to post a comparison for a non-compare 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 semi-direct 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 semi-direct (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 20-30 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.

 Parth04 November 5, 2014 08:18

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 00:57.