Computational Complexity

The most crucial phase of the mesh generation with respect to the computational complexity is the phase of the parametric tree building including the tree compatibility enforcement. Since a valid tree structure satisfying the ``1:2 rule'' is maintained throughout the whole tree building process, a horizontal tree traversal between two neighbouring cells can be efficiently implemented. The horizontal tree traversal can be then used to preserve the ``1:2 rule'' replacing the vertical tree traversal which exhibits the computational complexity. The vertical tree traversal is applied only in two cases - firstly, when the mesh size specification is extracted from a background parametric tree structure and secondly, during the tree compatibility enforcement. Since the parametric tree structure of boundary model entities is built simultaneously with the tree structure of non-boundary model entities, it can be used directly instead of extracting it from the tree structure of an appropriate non-boundary model entity. This reduces the use of the vertical tree traversal during the tree compatibility enforcement only to updating the tree structures of adjacent non-boundary model entities. Nevertheless, the time consumed by the vertical tree traversal is negligible compared to the total time required for the tree construction. The more important aspect is that the tree compatibility enforcement is an iterative process. It can be stated, however, that the number of iterations generally corresponds to the amount of the additional tree refinement which is adequate to the additional number of elements. Moreover, the ratio between the time spent in the raw tree building and the time consumed by the tree compatibility enforcement is increasing as the number of elements is increasing. Therefore the parametric tree building approaches the computationally complexity. The actual discretization is also of the computational complexity, which is a direct consequence of the application of templates that exhibits the constant computational complexity in average. Since the number of nodes in the final mesh is directly related to the number of elements, the nodal smoothing process, which is of the constant computational complexity on the level of a single node, does not introduce any additional source of complexity. The overall computational complexity of the presented discretization algorithm therefore approaches , which is in agreement with requirements put on mesh generators. In reality, however, the linear dependency between the number of elements and the generation time might not be necessarily observed. This is caused by the fact that the geometrical complexity of individual model entities (typically expressed in terms of their degrees) can be significantly different (by several orders of magnitude). Since the parametric tree building and point projection (used during the smoothing) is dependent on the geometrical complexity of model entities, the linearity of the relationship between the number of elements and the time can be severely disturbed. Note that this phenomenon does not occur if the model consists of model entities of a similar geometrical complexity or if uniform meshes are generated. In practice, the degree of individual model entities usually does not exceed the cubic one, which is sufficient to obtain the best performance.

*Daniel Rypl
2005-12-07*