3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Using a genetic algorithm to generate D‐optimal designs for mixture‐process variable experiments

This article presents and develops a genetic algorithm (GA) to generate D‐efficient designs for mixture‐process variable experiments. It is assumed the levels of a process variable are controlled during the process. The GA approach searches design points from a set of possible points over a continuous region and works without having a finite user‐defined candidate set. We compare the performance of designs generated by the GA with designs generated by two exchange algorithms (DETMAX and k‐exchange) in terms of D‐efficiencies and fraction of design space (FDS) plots which are used to evaluate a design's prediction variance properties. To illustrate the methodology, examples involving three and four mixture components and one process variable are proposed for creating the optimal designs. The results show that GA designs have superior prediction variance properties in comparison with the DETMAX and k‐exchange algorithm designs when the design space is the simplex or is a highly‐constrained subspace of the simplex.     

UNSTRUCTURED GRID GENERATION AND A SIMPLE TRIANGULATION ALGORITHM FOR ARBITRARY 2-D GEOMETRIES USING OBJECT ORIENTED PROGRAMMING

This paper describes the logic of a dynamic algorithm for a general 2D Delaunay triangulation of arbitrarily prescribed interior and boundary nodes. The complexity of the geometry is completely arbitrary. The scheme is free of specific restrictions on the input of the geometrical data. The scheme generates triangles whose associated circumcircles contain no nodal points except their vertices. There is no predefined limit for the number of points and the boundaries. The direction of generation of the triangles cannot be determined a priori as opposed to the moving front techniques. An automatic node placement scheme reflecting the initial boundary point spacings is used. The successive refinement scheme results in such a point distribution that the triangulation algorithm need not perform any geometric intersection check for overlapped triangles and penetrated boundaries. Further computational saving is provided by using a special binary tree (ADT) in which the points are ordered such that contiguous points in the list are neighbours in physical space. The method consists of a set of simple rules to understand. The dynamic nature of the Object Oriented Programming (OOP) of the algorithms provides efficient memory management on the insertion, deletion and searching processes. The computational effort bears a linear relation-ship between the CPU time and the total number of nodes. Some of the existing methods in the literature regarding triangular mesh generation are discussed in context. © 1997 by John Wiley & Sons, Ltd.     

Reed-Muller Codes on Complete Intersections

By using results and techniques from commutative algebra such as the vanishing ideal of a set of points, its a-invariant, the Hilbert polynomial and series, as well as finite free resolutions and the canonical module, some results about Reed-Muller codes defined on a zero-dimensional complete intersection in the n-projective dimensional space are given. Several examples of this class of codes are presented in order to illustrate the ideas. Received: March 11, 1999; revised version: November 6, 2000     

Pseudorandom numbers for conformal measures

We propose a new algorithm for generating pseudorandom (pseudo-generic) numbers of conformal measures of a continuous map T acting on a compact space X and for a Hölder continuous potential φ : X → ?. In particular, we show that this algorithm provides good approximations to generic points for hyperbolic rational functions of degree two and the potential ?h log |T′|, where h denotes the Hausdorff dimension of the Julia set of T.     

Adaptive tetrahedral mesh generation by constrained Delaunay refinement

This paper presents a tetrahedral mesh generation method for numerically solving partial differential equations using finite element or finite volume methods in three‐dimensional space. The main issues are the mesh quality and mesh size, which directly affect the accuracy of the numerical solution and the computational cost. Two basic problems need to be resolved, namely boundary conformity and field points distribution. The proposed method utilizes a special three‐dimensional triangulation, so‐called constrained Delaunay tetrahedralization to conform the domain boundary and create field points simultaneously. Good quality tetrahedra and graded mesh size can be theoretically guaranteed for a large class of mesh domains. In addition, an isotropic size field associated with the numerical solution can be supplied; the field points will then be distributed according to it. Good mesh size conformity can be achieved for smooth sizing informations. The proposed method has been implemented. Various examples are provided to illustrate its theoretical aspects as well as practical performance. Copyright © 2008 John Wiley & Sons, Ltd.     

A ‘best points’ interpolation method for efficient approximation of parametrized functions

We present an interpolation method for efficient approximation of parametrized functions. The method recognizes and exploits the low‐dimensional manifold structure of the parametrized functions to provide good approximation. Basic ingredients include a specific problem‐dependent basis set defining a low‐dimensional representation of the parametrized functions, and a set of ‘best interpolation points’ capturing the spatial‐parameter variation of the parametrized functions. The best interpolation points are defined as solution of a least‐squares minimization problem which can be solved efficiently using standard optimization algorithms. The approximation is then determined from the basis set and the best interpolation points through an inexpensive and stable interpolation procedure. In addition, an a posteriori error estimator is introduced to quantify the approximation error and requires little additional cost. Numerical results are presented to demonstrate the accuracy and efficiency of the method. Copyright © 2007 John Wiley & Sons, Ltd.     

A two‐level nonoverlapping Schwarz algorithm for the Stokes problem without primal pressure unknowns

A two‐level nonoverlapping Schwarz algorithm is developed for the Stokes problem. The main feature of the algorithm is that a mixed problem with both velocity and pressure unknowns is solved with a balancing domain decomposition by constraints (BDDC)‐type preconditioner, which consists of solving local Stokes problems and one global coarse problem related to only primal velocity unknowns. Our preconditioner allows to use a smaller set of primal velocity unknowns than other BDDC preconditioners without much concern on certain flux conditions on the subdomain boundaries and the inf–sup stability of the coarse problem. In the two‐dimensional case, velocity unknowns at subdomain corners are selected as the primal unknowns. In addition to them, averages of each velocity component across common faces are employed as the primal unknowns for the three‐dimensional case. By using its close connection to the Dual–primal finite element tearing and interconnecting (FETI‐DP algorithm) (SIAM J Sci Comput 2010; 32 : 3301–3322; SIAM J Numer Anal 2010; 47 : 4142–4162], it is shown that the resulting matrix of our algorithm has the same eigenvalues as the FETI‐DP algorithm except zero and one. The maximum eigenvalue is determined by H/h, the number of elements across each subdomains, and the minimum eigenvalue is bounded below by a constant, which does not depend on any mesh parameters. Convergence of the method is analyzed and numerical results are included. Copyright © 2011 John Wiley & Sons, Ltd.     

Fast and robust Delaunay tessellation in periodic domains

An algorithm is presented for constructing three‐dimensional Delaunay tessellations in periodic domains. Applications include mesh generation for periodic transport problems and geometric decomposition for modelling particulate structures. The algorithm is a point insertion technique, and although the general framework is similar to point insertion in a convex hull, a number of new issues are introduced by periodicity. These issues are discussed in detail in the context of the computational algorithm. Examples are given for the tessellation of random points and random sphere packings. Performance data for the algorithm are also presented. These data show an empirical scaling of the computation time with size of O(N^1.11) and tessellation rates of 7000–14000 tetrahedrons per second for the problems studied (up to 10⁵ points). A breakdown of the performance is given, which shows the computational load is shared most heavily by two specific parts of the point‐insertion procedure. Copyright © 2002 John Wiley & Sons, Ltd.     

Handling high-dimensional problems with multi-objective continuation methods via successive approximation of the tangent space

In many applications, several conflicting objectives have to be optimized concurrently leading to a multi-objective optimization problem. Since the set of solutions, the so-called Pareto set, typically forms a (k?1)-dimensional manifold, where k is the number of objectives considered in the model, continuation methods such as predictor–corrector (PC) methods are in certain cases very efficient tools for rapidly computing a finite size representation of the set of interest. However, their classical implementation leads to trouble when considering higher-dimensional models (i.e. for dimension n>1000 of the parameter space). In this work, it is proposed to perform a successive approximation of the tangent space which allows one to find promising predictor points with less effort in particular for high-dimensional models since no Hessians of the objectives have to be calculated. The applicability of the resulting PC variant is demonstrated on a benchmark model for up to n=100, 000 parameters.     

Response surface optimization for a nonlinearly constrained irregular experimental design space

Finding optimum conditions for process factors in an engineering optimization problem with response surface functions requires structured data collection using experimental design. When the experimental design space is constrained owing to external factors, its design space may form an asymmetrical and irregular shape and thus standard experimental design methods become ineffective. Computer-generated optimal designs, such as D-optimal designs, provide alternatives. While several iterative exchange algorithms for D-optimal designs are available for a linearly constrained irregular design space, it has not been clearly understood how D-optimal design points need to be generated when the design space is nonlinearly constrained and how response surface models are optimized. This article proposes an algorithm for generating the D-optimal design points that satisfy both feasibility and optimality conditions by using piecewise linear functions on the design space. The D-optimality-based response surface design models are proposed and optimization procedures are then analysed.     

A taxonomy of voting schemes for data fusion and dependable computation

Voting is an important operation in the fusion of data originating from diverse sources and in the realization of ultrareliable systems based on multiple computation channels. Voting involves the derivation of an output data object from a collection of n input data objects, as prescribed by the requirements and constraints of a voting algorithm. The objects voted on can be quite complex in terms of content and, explicitly specified or implicit, structure. Regardless of implementation details (e.g., whether realized in hardware, software, or hybrid schemes) and object space properties, voting algorithms can be classified according to how they view the input and output data objects and how they handle the votes (weights) at input and output. A 16-class (binary 4-cube) categorization results from dichotomizing each of the above voter features. This categorization leads to an abstraction that helps in the study of voting algorithms with regard to the dependability level for the outputs and the speed at which they are obtained; viz, the quality and efficiency of the algorithms. The taxonomy is broad enough to cover, and detailed enough to distinguish among, a wide variety of commonly used voting algorithms in data fusion and dependable computation. It also provides insight into the relationships of various voting schemes and facilitates comparison and fine-tuning of such algorithms.     

Adaptive solution strategy for solving large systems of p-type finite element equations

A solution strategy is proposed and implemented for taking advantage of the hierarchical structure of linear equation sets arising from the p-type finite element method using a hierarchical basis function set. The algorithm dynamically branches to either direct or iterative solution methods. In. the iterative solution branch, the substructure of the finite element equation set is used to generate a lower order preconditioner for a preconditioned conjugate gradient (PCG) method. The convergence rate of the PCG algorithm is monitored to improve the heuristics used in the choice of the preconditioner. The robustness and efficiency of the method are demonstrated on a variety of three dimensional examples utilizing both hexahedral and tetrahedral mesh discretizations. This strategy has been implemented in a p-version finite element code which has been used in an industrial environment for over two years to solve mechanical design problems.     

Nonlinear model order reduction based on local reduced‐order bases

A new approach for the dimensional reduction via projection of nonlinear computational models based on the concept of local reduced‐order bases is presented. It is particularly suited for problems characterized by different physical regimes, parameter variations, or moving features such as discontinuities and fronts. Instead of approximating the solution of interest in a fixed lower‐dimensional subspace of global basis vectors, the proposed model order reduction method approximates this solution in a lower‐dimensional subspace generated by most appropriate local basis vectors. To this effect, the solution space is partitioned into subregions, and a local reduced‐order basis is constructed and assigned to each subregion offline. During the incremental solution online of the reduced problem, a local basis is chosen according to the subregion of the solution space where the current high‐dimensional solution lies. This is achievable in real time because the computational complexity of the selection algorithm scales with the dimension of the lower‐dimensional solution space. Because it is also applicable to the process of hyper reduction, the proposed method for nonlinear model order reduction is computationally efficient. Its potential for achieving large speedups while maintaining good accuracy is demonstrated for two nonlinear computational fluid and fluid‐structure‐electric interaction problems. Copyright © 2012 John Wiley & Sons, Ltd.     

A C++ object-oriented toolkit for track finding with k-dimensional hits

A library is described for the recognition of tracks in a set of hits. The hits are assumed to be k-dimensional points (k-d), with k≥1, of which a subset can be grouped into tracks by using short-range correlations. A connection graph between the hits is created by sorting the hits first in k-d space using one of the developed, fast, k-space containers. The track-finding algorithm considers any connection between two hits as a possible track seed and grows these seeds into longer track segments using a modified depth-first search of the connection graph. All hit-acceptance decisions are called via abstract methods of an acceptance criterion class which isolates the library from the application's hit and track model. An application is tuned for a particular tracking environment by creating a concrete implementation for the hit and track acceptance calculations. The implementer is free to trade tracking time for acceptance complexity (influencing efficiency) depending on the requirements of the particular application. Results for simulated data show that the track finding is both efficient and fast even for high noise environments.     

Algorithm for converting 3D objects into rolls using spiral coordinate system

The article reports about the algorithm of converting objects into a flat ribbon in the process of roll powder sintering (RPS) additive manufacturing technology. The main idea of the author is to conform the transformation of spiral of Archimedes to 3D space. This algorithm is based on linear rolling effect. It is well known that any plane can be transformed into a roll and, in this way, the third dimension appears. Thus, two-dimensional space and height provide the conformity between (x, y, z) and (l, z) coordinates. This work describes how the algorithm of precise transformation of a 3D object to a flat ribbon, using the spiral coordinate system, has been designed and implemented with a varied layer thickness, a winding axle and resolution. The algorithm has been extensively tested with the help of several parts of computer aided design models based on the RPS process.     

Mobile Spatial coordinate Measuring System (MScMS) – introduction to the system

In many industrial fields (for example, automotive and aerospace) dimensional measurements of large size objects should be easily and rapidly taken. Nowadays, the problem can be handled using many metrological systems, based on different technologies (optical, mechanical, electromagnetic, etc.). Each of these systems is more or less adequate, depending on measuring conditions, a user's experience and skill, or other factors like time, cost, dimensions, accurateness, portability, etc. In general for measuring medium-large size objects, portable systems can be preferred to fixed systems. Transferring the measuring system to the measured object place is often more practical than vice-versa. The purpose of this paper is to introduce a new system called Mobile Spatial coordinate Measuring System (MScMS). The system has been designed to perform dimensional measurements of medium-large size objects. MScMS is made up of three basic parts: a ‘constellation’ of wireless devices, liberally distributed around the working area; a mobile probe to register the coordinate points of the measured object; and a PC to store data sent by the mobile probe?–?via Bluetooth?–?and to process them by means of ad hoc application software. MScMS is easily adaptable to different measuring environments and does not require complex procedures for installation, start-up or calibration. This document presents the system hardware/software/firmware architecture and functionalities and describes the peculiarities and metrological performances of MScMS first prototype, which has been developed at the industrial metrology and quality laboratory of DISPEA?–?Politecnico di Torino. Finally, the most critical aspects of MScMS are illustrated and the research perspectives for future improvements are given.     

Low‐frequency assessment of the in situ acoustic absorption of materials in rooms: an inverse problem approach using evolutionary optimization

The in situ assessment of the acoustic absorption of materials is often a necessity. The need to cover the whole frequency range of interest for the building engineer has led the authors to an approach involving two frequency‐complementary measurement methods. This paper deals with the part dedicated to low frequencies. The measurement is defined here as a boundary inverse interior problem. A numerical model of the room under investigation, allowing for the computation of the pressure field in the volume, given impedance boundary conditions and a point source, is combined to a global optimization algorithm. The algorithm explores the set of possible boundary conditions in order to minimize the difference between the computed pressure values and the one observed at a few measurement points, leading to the determination of all the boundary conditions at a time. In practice, the finite element method (FEM) or the finite difference method (FDM) is used here to model the room and an Evolution Strategy as the optimization tool. After describing the ES operators, a numerical study is carried out on simulated measurements, both on problem‐ and algorithm‐specific parameters, in the case of an academic two‐dimensional room geometry. The method is then applied to a three‐dimensional room with promising results. Copyright © 2002 John Wiley & Sons, Ltd.     

A fast algorithm for expansion over spherical harmonics

Algorithms for expansion over spherical harmonics are often used in electrostatic field calculation, calculation of the density functions in quantum chemistry and calculation of molecular surfaces. It usually includes expansion over spherical harmonics of degrees to several dozens. The usual method is to use an integration method over some grid on the unit sphere and in fact is a multiplication of the matrix of values of spherical harmonics in the grid points by a vector of values of the expanding function in the set of points. This algorithm executes O(NL²) operations whereN is the number of the grid points andL is the maximal degree of the spherical harmonics involved. We provide an algorithm of complexity O(NLlog² L) for multiplication of the matrix of values of spherical harmonics in points of an arbitrary grid on the unit sphere. The algorithm is based on interrelation between spherical harmonics and Legendre polynomials and on a fast algorithm for expansion over Legendre polynomials.     

A three‐dimensional model describing stress‐temperature induced solid phase transformations: solution algorithm and boundary value problems

An always increasing knowledge on material properties as well as a progressively more sophisticated production technology make shape memory alloys (SMA) extremely interesting for the industrial world. At the same time, SMA devices are typically characterized by complex multi‐axial stress states as well as non‐homogeneous and non‐isothermal conditions both in space and time. This aspect suggests the finite element method as a useful tool to help and improve application design and realization. With this aim, we focus on a three‐dimensional macroscopic thermo‐mechanical model able to reproduce the most significant SMA features (Int. J. Numer. Methods Eng. 2002; 55 : 1255–1264), proposing a simple modification of such a model. However, the suggested modification allows the development of a time‐discrete solution algorithm, which is more effective and robust than the one previously discussed in the literature. We verify the computational tool ability to simulate realistic mechanical boundary value problems with prescribed temperature dependence, studying three SMA applications: a spring actuator, a self‐expanding stent, a coupling device for vacuum tightness. The effectiveness of the model to solve thermo‐mechanical coupled problems will be discussed in a forthcoming work. Copyright © 2004 John Wiley & Sons, Ltd.