I have two general (and many sub- ) questions on grid-based computing. If you can answer any of them, especially on adaptivity, I would really appreciate it.

1) Automatic volumetric mesh generation:

What is the computational complexity of the state-of-the-art 3D mesh generators for Navier-Stokes? By complexity, of course, I mean what is the timing as a function of the number of nodes/cells/etc. If O(N) or O(NlogN) is the constant high?

Essentially, if one were to mesh a complex UNSTEADY geometry how much time would it take (roughly in terms of one computational timestep)? Note, meshing would have to be done every timestep, so we cannot amortize mesh generation cost over the simulation lifetime!

2) Mesh/grid adaptivity:

What is the computational complexity in this case?

Is adaptation faster or slower than mesh generation? How much is the cost per timestep compared to everything else? (say we want tolerance of 1.e-4 for vorticity)

Is it still true that (parallel) scalability is very poor for the poisson solution with adaptivity? or has the problem been solved?

What are the current issues with adaptation that need to be resolved?

Thanks in advance

Adrin Gharakhani

1. Mesh generation time will depend upon the type of mesh you are interested in. Since you are interested in "COMPLEX GEOMETRIES" you have the option of using Block Structured or Unstructured and Cartesian. As far as computation of COMPRESSIBLE VISCOUS FLOWS on CARTESIAN GRIDS are concernet, I would say that the technology is not well proven as yet and hence let me exclude it from my discussion. Similar case exists with unstructured grids also, but the situation is not as bad as far as LOW REYNOLDS NUMBER FLOWS are concerned. You are left with MULTI-BLOCK STRUCTURED GRID for your purpose. But the amount of time involved and the level of user interaction required make it more expensive compared to the UNSTRUCTURED GRIDS. For example you can generate a 2-D triangular unstructured grid around a complex geometry in few seconds whereas a BLOCK-STRUCTURED grid will take hours.

2. By adaption, you mean you are making a grid ADAPTED TO A PARTICULAR FLOW. Hence, each flow configuration will have different grid SPECIFICALLY GENERATED to SUIT THAT PARTICULAR FLOW FEATURES.

The COMPUTATIONAL COMPLEXITY stems from the fact that one has to generate an initial grid, compute the flow field on that initial grid and then re-generate/re-position the "points" wherever "gradients" are large which will result in a new grid (but, will remain largely as the old except for a region where the grid has been "adjusted") and then perform the computation again on the new grid. This "CYCLE" will be continued untill a "SATISFACTORY or GRID INDEPENDENT (?) " solution is obtained. Usually 3-6 levels of "adaptaion" is performed.

The answer to your question whether the adaption is faster or slower to mesh generation will depend upon the type of grid you choose. However, I can say that grid generation time would be the smallest for an unstructured grid generation using Delaunay triangulation technique.

My experience is limited and I am not in a position to answer your other questions.

However, I would strongly advice you not to use adaption and instead you can employ better Grid Generation and Numerical Techniques.

Good Luck,

CONSULTANT.

Hi Adrin,

The computational complexity of a mesh generation process is not solely dependent of the number of nodes. It is not even the dominating parameter. But if you plot time vs N for the grids I have generated over the years I would guess O(N^2/3) (you spend most of the time on the surface mesh generation).

More important for the time spent on grid generation is the problem you want to solve. Is it sufficient to solve the Euler equations? Fine, a grid is generated in no time. Are viscous effects important, but turbulence can be neglected? Alright, it is still fairly quickly done. But if you need to employ a two-equation turbulence model with Low-Reynolds number modification, you need to spend a lot of time with your grid. You get my point?

Concerning unsteady computations, there are tools to automatically account for moving boundaries in most commerical CFD codes. I have not used them myself so I cannot estimate the computational effort needed to apply them.

Grid adaptation is generally a quicker process than the grid generation. The cost is associated with the time you need to converge the solution again on the adapted grid. Depending on the state of your initial grid, the required accuracy of the solution and the adaptation algorithm, you may need to adapt in several steps.

In my view there are two main concerns in adaptation techniques today. 1) What is the best sensor to trigger adaptation in the right parts of the domain? 2) When you do surface mesh adaptation, how do you keep your original definition of the surface (which may be a CAD drawing or analytical functions in space).

Leonard Lorentzen

(1). You are talking about a very big issue, that is the grid generation in general. (2). In 2-D, you have only a few lines or curves to act as the boundary of the geometry. So, you can easily create a mesh or subdivide the domain with lines or curves and generate a multi-block mesh. (3). In 2-D, if you decide to take the numerical mesh generation approach instead of the algebraic method, then you have to solve a couple of partial differential equations. Then, the computing time of the mesh generation would be the time to solve the set of partial differential equations. So, it is faster to use algebraic mesh generation methods. (4). Since the mesh generation requires the distributions of nodal points along the boundary curves, the construction of the geometry, the visualization of the mesh and interactive operation with the mesh code, you will have to include these in the time estimation. Even though some mesh generation codes can automatically generate the final mesh, it is not push button operation. (5). The movement of a mesh, either due to the boundary conditions, the solutions, or the smoothing operations, require the similar operations as in the mesh generation. In other words, one can use either algebraic methods or numerical methods to readjust the mesh points or cells. (6). In 3-D, the problem is still related to the complexity of the geometry itself. Unless you are dealing with straight lines and flat plane surfaces, the geometry modeling alone will take one most of his time in generating the mesh. This is because a quality mesh does not like a highly skewed cell, and in order to reach this goal, both the geometry topology and the mesh topology (multi-block) must be studied in great detail first. (7). Then even after the creation of the first mesh, the subsequent adjustment to the mesh is even more difficult. In some cases, the nodes distribution along the boundary curve must be re-adjusted from patch to patch. And this can only be done looking at the 2-D screen and trying to change the setting with mouse. (8). So, if you are using the numerical grid generation apporach, the mesh generation will be slow. Otherwise, you would be spending a lot of time trying to identify which curve is which on the flat 2-D screen among many interconnecting curves, vertices, surfaces. (9). So, the 3-D geometry (you need this part ) and mesh generation is a very difficult problem to solve. So far, the approach is interactive, and it requires a lot of experience. (10). The unstructured mesh approach will reduce the overall time, but still, if you get some bad cells in a complex mesh problem, the solution to improve it is sometimes hard to find.

I guess this is a troll. Are we supposed to all go marching to www.aplied-scientific.com and discover grid-less CFD?

Hey,

Wait a minute !

WHAT IS GOING ON HERE....

Adrin Gharakhani, Sc.D.

the person who started this message chain - ISN'T HE FROM APPLIED-SCIENTIFIC ITSELF ?????

Check

http://www.applied-scientific.com/Employment.html

CONSULTANT

(1). In the cfd-forum, only the question and answer is important. The name is not. (2). Sometimes, it is possible to find a closed form solution. (3). Sometimes, it is possible to use singularity distribution to obtain a solution. (4). And in most cases, we have to subdivide the complex computational domain into tiny cells or grids to search for approximate solutions. (5). So, a name is nameless, unless the Q & A promotes the use of CFD. And even after that, a name is nearly nameless. (6). By the way, geometry and mesh is the essential part of modern CFD. The grid without a solution is only geometry, and the mesh independent solution will stay unchanged regardless of how one refine its mesh. So, the mesh becomes invisible. And the mesh is important because most of the time, the solution is mesh dependent. It's not only visible, but also affect the solution.

NO Offence, Please.

I just pointed out the coincidence. I agree that just the contents are important and not the names.

Even though people who have visited Applied-Scientific homepage might have noticed the coincidence, I just thought of pointing it out.

Well. Let me stop here on this subject.

CONSULTANT

> I guess this is a troll. Are we supposed to all go marching to www.aplied-scientific.com and discover grid-less CFD?

This is the most unprofessional insult on this forum, yet,and absolutely irrelevant to the questions I asked.

Adrin Gharakhani

> the person who started this message chain - ISN'T HE FROM APPLIED-SCIENTIFIC ITSELF ?????

Yes.

Was this information ever hidden from anyone? (it's clear from the email address in these messages)

As John Chien astutely pointed out, does it matter who posted the questions?

I asked these questions because I needed to know what the state-of-the-art is, since I've been away from it for 10 years now!

And yes ... Adrin Gharakhani, Sc.D.

Thanks for the valuable input

Adrin Gharakhani

> O(N^2/3) (you spend most of the time on the surface mesh generation).

Very interesting! Is the concern the correct specification of the geometry and making sure there are no incompatibilities, or does it somehow have to do with volumetric meshing? That is, do you need a good surface mesh in order to avoid degeneracy within the fluid domain or is there something more?

> More important for the time spent on grid generation is the problem you want to solve ...

I am looking into LES ... Obviously, if one is to claim accuracy one needs, at the very least, to reduce numerical diffusion - even with LES. So, I'd like to have adaptivity with automatic mesh generation before implementing any LES.

The problems of interest are unsteady flows in complex geometries. Then, in this case, what percentage of the flow simulation would be spent on automatic mesh generation and what percentage on adaptivity? (as a rough estimate) Perhaps, directly related to the latter is the question of the poisson solver. Are there complications in this case for parallelization?

> When you do surface mesh adaptation, how do you keep your original definition of the surface (which may be a CAD drawing or analytical functions in space)

Is this the complexity in surface meshing you alluded to earlier?

Thanks for the input

Adrin Gharakhani

Thanks for the input

Adrin Gharakhani

Eh, the original message didn't mention any web site and included a few very specific questions that certainly are of general interest to most CFDers - one of the best questions I've seen here lately. Adrin has also contributed a lot to this forum before by answering other peoples questions.

Hmm, I just realised I fell for your "troll" by answering your post .

(1). I would look at it from a different angle. This is because I spend most of my extra time taking pictures. By changing the camera angle or viewing angle, suddenly I can see a beautiful picture. (2). When a person is paying extra attention to someone's name and address or work, he is curious about this person. In other words, he is interested in this person or object. (3). When he is makeing a negative comment, he is testing the response of this person or object. (4). So, there is a good chance that this person can eventually become a good friend. (5). We are here to talk about the various issues of cfd. We are not here to say to everybody that "you are nice, you are beautiful, or you are from a well-known school." (6). This is a place where one can learn a lot from the messages posted. The key is how one interprets the messages, to his own advantages. (7). I think, it is important to have one's opinion. It is also important to stand behind one's opinion. Even in the most civilized society, the best one can make is to have 50% on his side. (8). When I was in the graduate school, we sometimes argued on a trivial issue in physics all night till next morning. Sometimes, people in management don't like the word "argue", but I think, it is essential to get the message through. " a vague message or comment" can only make the situation very unstable. (9). The better way to present the message is something like: " I've been away from the grid generation for a long time, even though grid-less approach is great, I still think there are room for me to make some contributions. I need your personal experience and comment in this area." (10). As for the response from one of the reader, he can say something like : " Is grid-less approach better than grid approach? What is your professional opinion on this? I don't think you are ready to accept a grid approach. Can you comment on this?" (11). By the way, this is a platform to exercise my brain to improve the blood circulation. (question like, Is Taiwanese a Chinese? Is Taiwan a part of China? Like Navier-Stokes equations, sometimes there is no obvious solutions.)

I am SORRY that I didn't notice your e-mail I-D. I should have checked before sending out that message. The moment I saw the web-address of Applied-Scientifice, I visited the site and I checked out the employment page. I was surprised and sent-out my message, thinking that it might have been a coincidence, in an act of impulse.

It was not my intention to divert the issue from genuine cfd discussions. You can see from the very few messages that I had posted.

Sorry if I have hurt your feelings.

CONSULTANT

Apology, of course, accepted.

Now back to what really matters - the original questions

Adrin Gharakhani

> What is the computational complexity of the state-of-the-art
> 3D mesh generators for Navier-Stokes? By complexity, of course,
> I mean what is the timing as a function of the number of
> nodes/cells/etc. If O(N) or O(NlogN) is the constant high?

I think you will have to narrow this down to a type of grid generator and what you want it to do. Simple analytical grids in, say, the combustion chamber of an IC engine are very fast, advancing front or constrained Delaunay unstructured are slow but point insertion/removal for adaptation is fast, high quality curvilinear grids for LES are very slow, ...

> Essentially, if one were to mesh a complex UNSTEADY geometry
> how much time would it take (roughly in terms of one computational
> timestep)? Note, meshing would have to be done every timestep,
> so we cannot amortize mesh generation cost over the simulation
> lifetime!

One would need to know the type of unsteady geometry and the unsteadiness in the flow. A complete blind regridding at each time step would be a pretty silly strategy for all but the simplest analytically specified grids. The task is obviously how to update the current grid to match the changing solution volume. Vertex insertion and removal in an unstructured grid does not hurt much in terms of computing times nor does driving a structured grid by specifying a function at each node. Other strategies such as overlapping grids for, say, dropping stores are more complex but quite viable.

> Is adaptation faster or slower than mesh generation? How much
> is the cost per timestep compared to everything else? (say we
> want tolerance of 1.e-4 for vorticity)

Depends on the type of mesh generation and the type of adaptation.

Is a tolerance of 1.0e-4 for vorticity a good error measure?

> Is it still true that (parallel) scalability is very poor for
> the poisson solution with adaptivity? or has the problem been
> solved?

I suspect the answer is that the problem is largely solved but can you indicate the types of solvers that have performed very poorly?

> What are the current issues with adaptation that need to be
> resolved?

What is a good general purpose error measure for engineers to use?

How to adapt for LES/accurate time varying flows?

> I am looking into LES ... Obviously, if one is to claim accuracy
> one needs, at the very least, to reduce numerical diffusion -
> even with LES. So, I'd like to have adaptivity with automatic
> mesh generation before implementing any LES.

I would strongly suggest that this is an unwise strategy if the objective is accurate unsteady flows. Adaptivity for RANS and adaptivity for LES are different. I would strongly recommend understanding what it is important to preserve in an LES simulation before "adapting" to "improve" things. Consider a vortex crossing from a region of high grid density to a region of low grid density. The better definition of the vortex on the high density grid will lead to a higher resolved dynamic component. What happens when the vortex crosses the interface? How is the energy injected/dissipated? Is it important?

> The problems of interest are unsteady flows in complex geometries.
> Then, in this case, what percentage of the flow simulation would
> be spent on automatic mesh generation and what percentage on
> adaptivity? (as a rough estimate) Perhaps, directly related to the
> latter is the question of the poisson solver. Are there
> complications in this case for parallelization?

We seem to be interested in the same problem (along with a lot of others I suspect). Unsteady flows in complex stationary geometries or moving geometries? If the latter is the unsteadiness in the geometry slow compared with the energy containing turbulence scales? Is the topology of the problem changing with time in a predictable (e.g. piston in IC engine) or unpredictable manner (bomb detaching from an aeroplane)? The reason I ask, of course, is because each is most efficiently addressed by different strategies.

PS What is a troll apart from a hairy beastie?

Excellent points.

> Simple analytical grids in, say, the combustion chamber of
> an IC engine are very fast, advancing front or constrained
> Delaunay unstructured are slow but point insertion/removal
> for adaptation is fast, high quality curvilinear grids for
> LES are very slow, ...

It is not sufficient to just be able to grid a geometry without considering its quality. For the IC engine problem, I've heard once a template is ready it takes seconds to generate a grid. BUT, it takes a while to create the template. If you wanted to try some new crazy design, then ... More importantly, I've seen the quality of these grids in many publications - they are simply a joke. You can't resolve the UNSTEADY jet shear layers, and the UNSTEADY recirculating/swirling/tumbling flows with a fixed grid, much less a coarse one. So smart adaptivity is required if one wants to learn something (and not just plot nice colors)

So, this is the type of problem I have in mind. I'm not interested in small (steady) problems.

But, what do you mean by slow or very slow (for LES)? compared to what? I don't have any reference point.

> Other strategies such as overlapping grids for, say,
> dropping stores are more complex but quite viable.

I think there are a lot of consistency issues (at the intersections of multiple blocks) that need to be resolved.

> Is a tolerance of 1.0e-4 for vorticity a good error measure?

The value was just an example, but the variable is the best measure in incompressible flow. I have seen (published) so-called converged results that show absolute junk for vorticity! I'd say if one wants to do a good job in capturing separation, vortex shedding, etc. one has to look into vorticity. (This is irrespective of the methodology used)

>> Is it still true that (parallel) scalability is very poor for
>> the poisson solution with adaptivity? or has the problem been
>> solved?

> I suspect the answer is that the problem is largely solved
> but can you indicate the types of solvers that have performed very poorly?

Can't really. Read it somewhere (don't recall)

>grid density to a region of low grid density. The better
> definition of the vortex on the high density grid will lead to a
> higher resolved dynamic component. What happens when the
> vortex crosses the interface? How is the energy
> injected/dissipated? Is it important?

Excellent point. Have to give it some thought. It seems then you need to alias LES into adaptation (if I make sense to you here)

Thanks for the thought provoking comments

Adrin Gharakhani

(1). I am not trying to answer your questions. I am just making some comments. (2). As I said before, this is a very big issue. (3). The grid quality issue was studied for more than 20 years with the "numerical mesh generation". In this approach, the mesh quality will be much better than that produced by the algebraic methods. The cost of the computing time is relatively high. you will have to solve several partial differential equations. The mesh quality is only part of the issue. And much of the effort and progress has been done by Joe Thompson and associates. We can say that this is the top of the line approach. (4). As I said before, a mesh without solution is just geometry. Even in that case, generating hundred of thousands of x,y and z in space itself is not trivial. (5). In order to make some sense out of a mesh, a good solution has to be generated. The adaptive mesh becomes the other part of the issue. This also has been studied for more than 20 years. (6). 3-D geometry is not a simple issue. A good 3-D mesh takes time to generate. A meaningful 3-D mesh which can provide accurate 3-D solution requires knowledge about the solution itself. (7). If one is still looking for a solution, then he has very little knowledge about it. Then he will have very little information to guide him to generate a good mesh. (8). Thus, the fine quality of "numerical mesh generation" remains largely a geometry issue. And the adaptive mesh without a good solution for guidance, simply does not know the right place to go. (9). If you adapt the mesh to the wrong solution, are you going to get back the right solution? (10). The problem is "we don't know the solution, because we are looking for it". And if you have the solution, then we would not be looking for it. And when a joke cease to be a joke, the problem is solved.