I would like to post a question on efficient iterative methods for solving linear equations arising in CFD problems when FE, FD and FV methods are employed. Of course, there are so many different CFD and CFD related problems. However, there are not so many efficient iterative solvers for indefinite non-symmetric systems. Is it true? Trying to start this discussion I would like to advocate Krylov subspace methods with ILU preconditioning when unstructured grids are used. This combination is, however, well known. I wonder if anybody know any good alternative proved to be efficient for a large class of INDUSTRIAL CFD problems. Maybe someone will find this question to be totally incorrect. This would be also very interesting.

In very general case, i.e. a grid is completely unstructured, this combination (GMRES+ILU) is probably one of the best choices (relatively simple and very robust). If the grid is, for instance, multilevel, i.e. has been generated using several (local or global) refinement steps, starting from some coarse grid, then the multigrid method (with ILU as a smoother) could be a good alternative. Personally, I try to avoid nonsymmetric problems. If the problem is essentially time-dependent, than I would use the method of characteristics.

There are quite many related works in SIAM´s journals, I might recommend the SIAM J. Sci. Stat. Comput., and naturally J. Comput. Phys.

With best regards

Of course, I am aware of numeriuos papers in SIAM J. devoted to this question. But in my posted message I am more interested in experience of solving practical CFD problems. Nevertheless, if you could indicate in SIAM good papers devoted to practical rather than theoretical aspects of iterative methods for CFD problems I would appreciate it very much.

With my best regards

Vitaly Bulgakov

>Maybe someone will find this question to be totally incorrect. This would be also very interesting.

Hi, Vitaly.

Not that I think your question to be incorrect, but you sound practical, and here is a comment from a practical viewpoint.

There is a huge amount of public domain software for solving linear algebraic systems. This software was developed by large groups of highly qualified programmers and algebra gurus working for many years (yes, so!) to make the code more efficient, and they continue to improve it. Our problems are not very different from many others, as far as linear systems are concerned. Therefore, it is hard to compete with existing codes. It is more practical to concentrate on building that linear system, on schemes etc., and use existing software for solving them. Surely, if you will spend a year on improving the scheme while using a standard subroutine your code will be faster than if you spend the same time on creating your own linear equation solver.

If you, nevertheless, wish to compare various solvers in the case of your particular problem (not a bad idea, too), download several and enjoy. A good starting point is

http://www.utexas.edu/cc/math/softwa...ic_domain.html

It is also useful to go to a search engine and type something like

sparse matrix iterative public domain +download

the latter to cut off pages which are talking about the software but do not provide it.

It is widely acknowledged that one of the most important abilities of a professional programmer is the ability to use library subroutines. Saves years of hard work, really, and not a joke.

Sorry, if you are not after a practical solution then the above is irrelevant, and I feel that discussion of various solvers can be interesting for me, too.

Hope you find this worth reading.

Yours Sergei

Sure. If you need to develope a solver from scratch and this is just a part of a big project, the only way is probably to take it from some public domain library. Needless to say how many people, especially those tailoring their Ph.D's or some research projects took advantage of this nice internet possibilities. God bless those people who kindly wish to share their developments. I would myself advocate this way in many situations as I got a lot of good working programs from the public domain. It's however different if you are doing something long-term and have a certain background in this field.

I am still interested to proceed this discussion about efficient iterative solvers for CFD problems. Is there something more efficient than the combination of ILU + Krylov subspace methods for nasty CFD problems on unstructured grids.

Did anybody here about combinatorial based preconditioners? How it is related to ILU?

With my best regards.

OK, good. In fact, I could now risk to implement something more efficient for my specific program myself (but what I told earlier was true), if somebody would tell me what is the best. While waiting for someone more qualified than me:

A shot in the air: do you know what is the Fedorenko method? I do not know myself, just several days ago a fellow programmer mentioned it as extremely efficient (well, he was talking about it being ten or even a handred times faster than all the rest?!) in CFD problems but difficult to implement, and another one was telling something like this a month ago, but I had no chance to learn the details. Some doubling was mentioned, but I did not understand. It is iterative. I had an impression that Fedorenko method was for matrices corresponding to structured grids, but I am not sure. If you do not know, too, it might be worth investigating.

Sergei

Yes, I know. Fedorenko method (now called multigrid) is in short the method which takes advantage of the coarse grid solution. After so called smoothing (standard iterations) the residual contains only slowly oscilating terms and therefore can be reduced to the coarse grid and provide a coarse grid (correction) solution which is inexpencive. This correction is added to the vector of smoothing iterations and smoothing is continued. This process is looped. The most important issue here is to construct a coarse-fine prolongation which is usually possible only on structured meshes. There are different multigrid schemes: V, W, etc. There are multi-level preconditioners based on the multigrid. There are algebraic multigrid or algebraic-like multigrid methods with and without contruction of the coarse model, etc., etc.... Actually I worked in this field for a long time, but more for structural problems. The multi-level aggregation method is one example of this work.

The use of multigrid or related methods in CFD with unstructured grids (and not hierarhical grids caused by the refinement processes) is very interesting. It is also interesting if the convection dominated equations are still good for the multigrid treatment.

No doubts these questions have been many times discussed in literature and conferences. Nevertheless, why not to refresh it, especially in the context of applications to "nasty" CFD problems on unstructured grids.

With my best regards.

It is a good idea to describe the situation in a somewhat easier to understand terms, (1). what is Krylov subspace method? ,(2). what is ILU preconditioning? (3). what is the characteristics of the linear matrix when using unstructured gird? (4). what is your definition of "efficient method"? I may not be able to give you the answer, but I am sure that we all can learn something from the discussions if the background of the question is more visible to us. Could you give us a reference where the methods mentioned were used in the CFD application?

Thanks a lot. Multigrid I know. Funny thing is these changes of names. I had a lot of trouble trying to understand why people in the West used Thomas method instead of what I knew as 'progonka' in Russian, and what was a difference! But knowing multigrid and not knowing Fedorenko beats it!

And again thanks for this remarkable remark:

>It is also interesting if the convection dominated equations are still good for the multigrid treatment.

Indeed, in high-Re separated flow, for example, we can expect large gradients across the dividing streamline. Coarse grid cannot resolve them. However, large scale corrections can result in shifting the dividing streamline, which, hence, has to be accounted for in smooth-scale iterations. But since this shift is a large-scale effect, the convergence will be slow. I see the problem and like it. Never thought about it. Very interesting. May be, the knowledge accumulated in high-Re asymptotics studies can help to resolve this. If we could know where to shift the small-scale solution when the large scale correction is found, that would be all right. I should think about this. Thank you.

>The use of multigrid or related methods in CFD with unstructured grids (and not hierarhical grids caused by the refinement processes) is very interesting.

So, it is a hierarchy, not structure, which is important. That would be understandable. What if the grid is built as a fractal? It would be what I would call unstructured (anyway, certainly much more flexible than usual structured grids) and still it has an intrinsic self-similarity.

Kghm. I am solving steady compressible subsonic NSE (with turbulence models) by Newton method, with linear system solved by a direct method, as a band-matrix. Simple, fast, but memory-consuming, and a super-computer is not always at hand, you know. So I am thinking about switching to iterative method, but am afraid that minimizing residuals or what-do-you-call-it will be too slow. Do you think multigrid can help? No, my flows are separated. So, what would be your choice? And is your choice available as public-domain subroutine?

Yours Sergei

Usually multigrid positive effects are explained by the fact that slow portion related to first eigenvectors of the elliptic problem (like Laplas, Elasticity, etc.) can be suppressed by the coarse grid. I guess this property is not preserved in such problems like those with high-Re separated flow and many others in CFD. However the coarse model can be constructed in such a way that on the subspace based on the prolongation from this coarse model the original matrix and the multi-level preconditioner coinside. This is the case in the aggregation technique where aggregates do not exactly serve as a coarse grid but provide an excelent convergence. What I am saying is that maybe it's possible to construct a sort of flow aggregation model?, say for separated flow.

Regarding my choice for your problems. I do not have it, but would be interested to know about experience of using ILU-based iterative methods for this purpose. Did you try or hear about such an experience?

1) and 2) can be found in papers and textbooks related to iterative solution of sparse systems. A good choise may be a book of Yousef Saad (iterative methods for sparse linear systems, 1996).

Matrices resulted from unstructured grids are just sparse matrices without any special structure so that it is difficult to use iterative methods related to differential equations, like those taking advantage of the finite-difference approximation, like alternate direction methods, for example. So some "black box" approaches should be used for iterative solutions.

Efficient iterative method is the method with fast convergence and operations for a wide range of problems.

Regards

>What I am saying is that maybe it's possible to construct a sort of flow aggregation model?, say for separated flow.

Sorry, this is above my head. What is the aggregation model?

>to know about experience of using ILU-based iterative methods for this purpose. Did you try or hear about such an experience?

Sorry again, my idea about ILU is very uncertain. Is it some kind of approximate decomposition? May be again the terminology problem.

I do read papers on numerical calculations of separated flows. I never met anything which I would call unconventional. In the turbulent case the main problem is the turbulence model, this is where the efforts are concentrated. In high-Re steady laminar the calculations are explicitly of research character: the code is written to perform a small number of calculations and then be thrown away. So, what I wrote in my first message applies.

One exception may be the attempts to use marching schemes in steady problems with second derivatives in the marching direction and some other terms taken as a source term from the previous iteration. They were not entirely successful, although there was an interesting connection between some tricks needed to stabilize the calculations and the theory of viscous-inviscid interaction. Well, this is irrelevant to iterative linear solvers, I am afraid.

Hello Vitaly, I can solve VERY nonsymmetric large systems for hydraulic problems (plus nonlinear) and there are proof and method.

There are realy INDUSTRIAL application.

Please see cmm.univer.omsk.su/kbks

Regards

I think you are looking at the CFD problems from the mathematical point of view, that is looking at the final algebraic equations. Since CFD problems are fluid dynamics problems, it is related to the physics of fluid dynamics, such as continuity, diffusion processes due to viscosity, mixing, convection processes, and production etc. The diffusion part is confined by the boundary of the problem. So the distance away from the wall or boundary is an important parameter. This can be seen in the low Reynolds number flows or heat conduction problems. In these situations, if the mesh is aligned with the iso-thermal lines, you are likely to get fast convergent and accurate solutions. On the other hand, with unstructured mesh, it is really hard for each cell to properly communicate with the boundary. The unstructured mesh really is just a geometry problem which has nothing to do with the physics at all!!! Therefore, one really need to look at the CFD solution first, then construct the mesh next, so that the mesh can have some physics included. I think, this is very important. The sparse, irregular matrix created is simply because the person is only trying to solve the geometry problem at that point without any knowledge of physics. And the multi-grid method is physics, it is not mathematics. It is ideal for the elliptic problems.For the convection processes, the direction of the velocity vector ( or the equivalent one) is the controlling parameter in the processes. That is why there are methods such as the up-wind methods, which are derived from the physics not the mathematics. With the convection processes, the streamlines becomes important parameters to guide the mesh generation. If the mesh is aligned with streamlines, the error will be minimized, and the convergence improved. The unstructured mesh tends to destroy this important directional parameter. When the source term is important, the flow is coupled, and it must be solved implicitly. All these factors simply tell us that the solution to the fluid dynamics problem is physics dominated, not geometry or mathematics dominated. The need to use the unstructured mesh is mainly due to convenience, that is, it is easier for the users to create a mesh for the solver without regarding to the ultimate physics of the fluid dynamics. So, after having disturbed the well organized physical system in an unstructured way and then trying to get the underlined physics back from the sparse,irregular matrix, is itself a self-created hardship. For me, over the years, I have used point iterative methods and at most the line iterative methods for simplicity and ease of programming, for all 2-D and 3-D low speed problems. And think, the same principle applies to the compressible flow formulation as well. One really need to look at the physics first before he can come up with an accurate and efficient method for CFD. In 2-D, it may be possible to look at the appearance of the matrix and try to re-arrange it. For 3-D, once the connectivity of the physical system is disturbed, it is hard to get help from the physics of the problem to improve the accuracy and the efficiency. With exception that,a great mathematician may be able to decode the physics by looking at the resulting sparse, irregular matrix. So the solution along this route is still wide open. ( the use of the boundary layer coordinates to solve the boundary layer problem is a very good example of creating a mesh which includes physics. Many unstructured codes are re-discovering this feature through the use of quad mesh or a hybrid mesh near a wall. Such feature should also be applied in the flow field where a boundary layer or a shear layer exist away from the wall for accuracy and efficiency.)

Thank you very much for your letter. I completely agree with every word in it. The same situation is in the structural analysis. All this automatization stuff shades physical meaning. But fluid problems even more sensitive to this.

Nevertheless, FE shape functions can also have upwind modifications and it's enough to have unstructured mesh only in some parts of the problem domain to make line iterative methods not applicable. Besides, I am not sure that even if the mesh has logically rectangular structure which nicely serves for the physics, the line methods will work for all problems. What is your opinion?

>What I am saying is that maybe it's possible to construct a sort of flow aggregation model?, say for separated flow.

Sorry, this is above my head. What is the aggregation model?

Look at the coarse grid in multigrid as some coarse model. You may use some simplified formulation, say, for the stream in a part of your problem domain which will have less degrees of freedom etc. The aggregation model is a substitution to the coarse grid when this grid is difficult to construct.

>to know about experience of using ILU-based iterative methods for this purpose. Did you try or hear about such an experience?

Sorry again, my idea about ILU is very uncertain. Is it some kind of approximate decomposition? May be again the terminology problem.

Yes, this is approximate decomposition. However there

so many ways, and some of them are now standard, to

perform this decomposition. So saying ILU iust indicates a type of the preconditioning and will need

more details in further considiration.

I do read papers on numerical calculations of separated flows. I never met anything which I would call unconventional. In the turbulent case the main problem is the turbulence model, this is where the efforts are concentrated. In high-Re steady laminar the calculations are explicitly of research character: the code is written to perform a small number of calculations and then be thrown away. So, what I wrote in my first message applies.

One exception may be the attempts to use marching schemes in steady problems with second derivatives in the marching direction and some other terms taken as a source term from the previous iteration. They were not entirely successful, although there was an interesting connection between some tricks needed to stabilize the calculations and the theory of viscous-inviscid interaction. Well, this is irrelevant to iterative linear solvers, I am afraid.

Anyway you will solve the linear equation system in

each time step or non-linear iteration step. Right?

So, when you have a large scale problem you will

need to solve this system more efficiently.

There are two approaches1). connected multi-block mesh. In this way one can move into small areas with fine structured mesh at the same time, one can cover the whole domain. This approach requires additional control of new block boundaries. This approach is currently widely used. (2). overlapped multi-block mesh. In this way, one is actually solving several coupled problems, and each one is well structured and can be solved efficiently. The information transfer is through the overlapped region. This approach makes the movement of the geometry boundary easier to handle. In most cases, there is really no need to make the mesh highly unstructured or even random. As a matter of fact, a boundary aligned mesh ( just for the boundary region) overlapped on a simple Cartesian mesh may be more efficient than a single unstructured boundary aligned mesh for the whole domain. The idea is to simplify the formulation before getting to the point of solving a large ,sparse, irregular matrix. But, on the other hand, if an efficient solver can be found for highly unstructured mesh, then it really doesn't matter how you mesh the problem at all. Sometimes, the hardware speed-up is easier to achieve.

If I develope in-house CFD code I would follow these concepts. Actually, some years ago I started with topologically regular grids on rectangular domains using fictitious finite elements. We managed to model very serious 3D industrial structural analysis and heat conduction problems of complex shape. Besides, the multigrid method nicely took advantage of this and helped us to solve huge problems on slow computers.

When you say the connected muli-block mesh is currently used, do you mean commercial software which works in hands of customers and therefore should supply them with a friendly preprocessing tools?

What kind of iterative methods are used for solving linear systems in multi-block and overlapped multi-block mesh applications?

A very good example is the MegaCads Multiblock-Elliptic-Grid-Generation...system posted here recently by Olaf Brodersen, developed for complete transport aircraft. I think they use both the connected and overlapped types. The web site is http://beasgi2.ea.bs.dlr.de/megacads/ . The message was posted recently here, you should be able to find it by using "search" command. As for the methods to solve the final algebraic equations, I think, it depends on the governing equations in the solver, and each commercial code probably uses different approaches. The multi-block structured mesh in MegaCads is really the right approach to a complex problem. It is also good for accuracy. As I said, in this approach, you need to do some extra work. but that is exactly the difference between an expert and an average engineer. The unstructured mesh approach will save time in the mesh generation stage and is good for average engineers. So, the definition of an efficient method must also take into consideration of the experience of the user and his working environment.