A spectral multipole method for efficient solution of large-scale boundary element models in elastostatics

In this paper we introduce a method to reduce the solution cost for Boundary Element (BE) models from O(N³)operations to O(N²logN) operations (where N is the number of elements in the model). Previous attempts to achieve such an improvement in efficiency have been restricted in their applicability to problems with regular geometries defined on a uniform mesh. We have developed the Spectral Multipole Method (SMM) which can be used not only for problems with arbitrary geometries but also with a variety of element types. The memory necessary to store the required influence coefficients for the spectral multipole method is O(N) whereas the memory required for the traditional Boundary Element method is O(N²). We demonstrate the savings in computational speed and fast memory requirements in some numerical examples. We have established that the break-even point for the method can be as low as 500 elements, which implies that the method is not only suitable for extremely large-scale problems, but that it also provides a useful bridge between the small-scale and large-scale problems. We also demonstrate the performance of the multipole algorithm on the solution of large-scale granular assembly models. The large-scale BE capacity provided by this algorithm will not only prove to be useful in large macroscopic models but it will also make it possible to model microscopic damage processes that form the fundamental mechanisms in plastic flow and brittle fracture.     

Fast multipole method as an efficient solver for 2D elastic wave surface integral equations

The fast multipole method (FMM) is very efficient in solving integral equations. This paper applies the method to solve large solid-solid boundary integral equations for elastic waves in two dimensions. The scattering problem is first formulated with the boundary element method. FMM is then introduced to expedite the solution process. By using the FMM technique, the number of floating-point operations of the matrix-vector multiplication in a standard conjugate gradient algorithm is reduced from O(N ²) to O(N ^1.5), where N is the number of unknowns. The matrix-filling time and the memory requirement are also of the order N ^1.5. The computational complexity of the algorithm is further reduced to O(N ^4/3) by using a ray propagation technique. Numerical results are given to show the accuracy and efficiency of FMM compared to the boundary element method with dense matrix.     

A fast multi‐level convolution boundary element method for transient diffusion problems

A new algorithm is developed to evaluate the time convolution integrals that are associated with boundary element methods (BEM) for transient diffusion. This approach, which is based upon the multi‐level multi‐integration concepts of Brandt and Lubrecht, provides a fast, accurate and memory efficient time domain method for this entire class of problems. Conventional BEM approaches result in operation counts of order O(N²) for the discrete time convolution over N time steps. Here we focus on the formulation for linear problems of transient heat diffusion and demonstrate reduced computational complexity to order O(N^3/2) for three two‐dimensional model problems using the multi‐level convolution BEM. Memory requirements are also significantly reduced, while maintaining the same level of accuracy as the conventional time domain BEM approach. Copyright © 2005 John Wiley & Sons, Ltd.     

Sequential and parallel schemes for adaptive 2-D parameter estimation with application to image estimation

In this paper, the non-causal quarter plane 2-D Recursive Least Squares (2D-RLS) algorithm for adaptive processing is developed. The complexity of this algorithm turns out to beO(L ⁶) per iteration, for anL ×L window. With the aim of reducing this complexity, the matrix gains appearing in the algorithm are replaced by scalar gains. This approach yields the Approximate 2-D Recursive Least Squares (A2D-RLS) algorithm, which is shown to have a complexity ofO(L ²). With the objective of reducing the computation time even further, a parallel scheme is developed for the A2D-RLS algorithm. Since the algorithm is inherently sequential, its parallelization involves some more approximations. The desired accuracy of the estimated parameters is shown to place an upper bound on the number of processors. The parallel scheme is suitable for implementation on shared memory as well as distributed memory machines. The algorithm is applied to the problem of image estimation. Simulation results giving speed-up, efficiency, and the accuracy of the estimated image are presented.     

Source-sink flow in a rotating cylinder

Summary This paper describes the axisymmetric source-sink flow in a rapidly rotating cylinder. Relative fluid motion is induced by the presence of a sink in the bottom corner and a ring source located somewhere in the fluid, at some distance from the solid boundaries. In order to neglect nonlinear effects the volumetric flow rates are assumed to be small, i.e. O(E ^1/2), with E the Ekman number of the flow. The transport from the source to the sink is carried by Ekman layers at the end caps, and a Stewartson layer at the sidewall. At the ring source a free Stewartson layer arises, in which the injected fluid is transported towards the Ekman layers. This Stewartson layer consists of layers of thicknesses E ^1/4 and E ^1/3, which both contribute to the vertical O(E ^1/2) transport. The ring source is enveloped by a ring-shaped region of cross-sectional dimensions O(E ^1/2 × E ^1/2), in which the injected fluid is rearranged before erupting into the E ^1/3 layer. As E ^1/2 E ^1/3, this region appears as an isolated singularity in the E ^1/3 layer; in fact it consists of a combination of an upward and a downward directed source, the strengths of which can be determined by transport arguments. The paper presents an analysis of the E ^1/3-layer structure on the basis of a linear theory; it also describes how the analysis can be extended to the situation in which fluid is injected through an array of sources at different heights.     

A wideband fast multipole algorithm for two‐dimensional volume integral equations

This paper describes a wideband fast multipole algorithm (FMA) for the computation of two‐dimensional volume integral equations. Our previous paper presented the wideband FMA by switching between the diagonal and non‐diagonal forms according to cell size and required accuracy. In order to improve the efficiency of the algorithm, we use interpolation and filtering techniques. Moreover, we introduce a simple and efficient way to store sequences of the special functions and their discrete Fourier transforms. Numerical examples show that the computational and memory complexities are reduced from O(N²) to O(N), where N is the number of square elements followed by the discretization of the volume integral equations. The computation results show very good agreement with the analytical solutions. We present some numerical results for the computation of scattering from a cylindrical object with sharp edges and a Gaussian‐like inhomogeneous cylinder. Copyright © 2008 John Wiley & Sons, Ltd.     

Fast parallel algorithms for the Maximum Empty Rectangle problem

We present efficient parallel algorithms for the maximum empty rectangle problem in this paper. On crew pram, we solve the area version of this problem inO(log ² n) time usingO(nlogn) processors. The perimeter version of this problem is solved inO(logn) time usingO(nlog ² n) processors. On erew pram, we solve both the problems inO(logn) time usingO(n ²/logn) processors. We also present anO(logn) time algorithm on a mesh-of-trees architecture.     

On the development of characteristics in an oseillating,rotating fluid

Summary A source of fluid with an oscillatory strength, which is situated on the axis of a rotating fluid, commences to act at time t=0. We describe how inviscid, geostrophic forces lead to the development of the characteristic cone when the frequency of oscillation is less than twice the frequency of rotation. Eventually, viscous forces become important when the time is O(E ^-1/3), where E is the small Ekman number, in forming the thin shear layer along the surface of the cone.     

Parallel multipole implementation of the generalized Helmholtz decomposition for solving viscous flow problems

The evaluation of a domain integral is the dominant bottleneck in the numerical solution of viscous flow problems by vorticity methods, which otherwise demonstrate distinct advantages over primitive variable methods. By applying a Barnes–Hut multipole acceleration technique, the operation count for the integration is reduced from O(N²) to O(NlogN), while the memory requirements are reduced from O(N²) to O(N). The algorithmic parameters that are necessary to achieve such scaling are described. The parallelization of the algorithm is crucial if the method is to be applied to realistic problems. A parallelization procedure which achieves almost perfect scaling is shown. Finally, numerical experiments on a driven cavity benchmark problem are performed. The actual increase in performance and reduction in storage requirements match theoretical predictions well, and the scalability of the procedure is very good. Copyright © 2003 John Wiley Sons, Ltd.     

Optimizing Two-Level Supersaturated Designs Using Swarm Intelligence Techniques

Supersaturated designs (SSDs) are often used to reduce the number of experimental runs in screening experiments with a large number of factors. As more factors are used in the study, the search for an optimal SSD becomes increasingly challenging because of the large number of feasible selection of factor level settings. This article tackles this discrete optimization problem via an algorithm based on swarm intelligence. Using the commonly used E(s²) criterion as an illustrative example, we propose an algorithm to find E(s²)-optimal SSDs by showing that they attain the theoretical lower bounds found in previous literature. We show that our algorithm consistently produces SSDs that are at least as efficient as those from the traditional CP exchange method in terms of computational effort, frequency of finding the E(s²)-optimal SSD, and also has good potential for finding D₃-, D₄-, and D₅-optimal SSDs. Supplementary materials for this article are available online.     

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.     

A memory-economic frontwidth reduction algorithm

A simple element numbering algorithm is described which yields near-minimal frontwidths for two- and three-dimensional finite element assemblies. Renumbering of E elements requires an immediate-access computer memory size which is proportional to the square root of E in two-dimensional problems, and to the two-thirds power of E in three dimensions. This very small memory requirement allows processing of large problems in minicomputers. When used in large computers, page-swapping operations are minimized.     

Fracture and fragmentation of simplicial finite element meshes using graphs

An approach for the topological representation of simplicial finite element meshes as graphs is presented. It is shown that by using a graph, the topological changes induced by fracture reduce to a few, local kernel operations. The performance of the graph representation is demonstrated and analyzed, using as reference the three‐dimensional fracture algorithm by Pandolfi and Ortiz (Eng. Comput. 1998; 14 (4):287–308). It is shown that the graph representation initializes in O(N) time and fractures in O(N) time, while the reference implementation requires O(N) time to initialize and O(N) time to fracture, where N_E is the number of elements in the mesh and N_I is the number of interfaces to fracture. Copyright © 2007 John Wiley & Sons, Ltd.     

Mapping stereo and image matching algorithms onto parallel architectures

In this paper we present parallel implementations of two vision tasks; stereo matching and image matching. Linear features are used as matching primitives. These implementations are performed on a fixed size mesh array and achieve processor-time optimal performance. For stereo matching, we proposeO(Nn ³/P ²) time algorithm on aP ×P processor mesh array, whereN is the number of line segments in one image,n is the number of line segments in a window determined by the object size, andP ⩽n. The sequential algorithm takesO(Nn ³) time. For image matching, a partitioned parallel implementation is developed.O[((nm/P ²) +P)nm] time performance is achieved on aP ×P processor mesh array, whereP ² ⩽nm. This leads to a processor-time optimal solution forP ⩽ (nm)^1/3. This research was supported in part bynsf under grantiri-9145810 and in part bydarpa andafosr contracts F-49260-89-C-0126 and F-49620-90-C-0078.     

Calculation of the Optical Spectra of Fluorite

Experimental, experimental–calculated, and theoretical absorption, reflection, and E ²₂(E) spectra of fluorite crystals were analyzed in the range 6–35 eV. General trends and characteristic features of the spectra were revealed, and the most reliable R(E) data were identified. The experimental–calculated (E) and E ²₂(E) data were shown to agree well with predictions of two theoretical models.     

Laser-induced surface decomposition of Al2O3 excited in the V-center absorption band

The primary products of desorption from Al₂O₃ surface excited by laser pulses (pulse duration τ∼15 ns; wavelength λ=354 nm, radiant power density P/S<10⁸ W/cm²) in the V-center absorption band were studied by the time-of-flight (TOF) spectroscopy. The TOF spectra show evidence of the desorption of one “ cold” (T ₁=300 K) and two “hot” (T ₂=1000 K, T ₃=4300 K) groups of oxygen molecules with the Maxwell velocity distributions, as well as of the hot Al and O atoms with nonequilibrium energy distributions (E ₁=0.37 eV, E ₂=0.38 eV). A model describing the oxygen desorption as initiated by the electron transitions is suggested, in which escape of the cold O₂ molecules from the surface is related to discharge of the O ₂ ⁻ anions adsorbed on the V-centers, desorption of the hot atoms is attributed to discharge of the surface O⁻ anions, and the appearance of the hot O² molecules is related to the associative desorption of two O⁻ anions localized at the same V-center discharged by a pair of excitons.     

Trade-Off between Efficiency and Effectiveness: A Late Fusion Multi-View Clustering Algorithm

Late fusion multi-view clustering (LFMVC) algorithms aim to integrate the base partition of each single view into a consensus partition. Base partitions can be obtained by performing kernel k-means clustering on all views. This type of method is not only computationally efficient, but also more accurate than multiple kernel k-means, and is thus widely used in the multi-view clustering context. LFMVC improves computational efficiency to the extent that the computational complexity of each iteration is reduced from O(n³) to O(n) (where n is the number of samples). However, LFMVC also limits the search space of the optimal solution, meaning that the clustering results obtained are not ideal. Accordingly, in order to obtain more information from each base partition and thus improve the clustering performance, we propose a new late fusion multi-view clustering algorithm with a computational complexity of O(n²). Experiments on several commonly used datasets demonstrate that the proposed algorithm can reach quickly convergence. Moreover, compared with other late fusion algorithms with computational complexity of O(n), the actual time consumption of the proposed algorithm does not significantly increase. At the same time, comparisons with several other state-of-the-art algorithms reveal that the proposed algorithm also obtains the best clustering performance.     

LFTB: An Efficient Algorithm to Bound Linear Fractional Transformations

This work presents an efficient algorithm to solve a structured semidefinite program (SDP) with important applications in the analysis of uncertain linear systems. The solution to this particular SDP gives an upper bound for the maximum singular value of a multidimensional rational matrix function, or linear fractional transformation, over a box of n real parameters. The proposed algorithm is based on a known method for solving semidefinite programs. The key features of the algorithm are low memory requirements, low cost per iteration, and efficient adaptive rules to update algorithm parameters. Proper utilization of the structure of the semidefinite program under consideration leads to an algorithm that reduced the cost per iteration and memory requirements of existing general-purpose SDP solvers by a factor of O(n). Thus, the algorithm in this paper achieves substantial savings in computing resources for problems with a large number of parameters. Additional savings are obtained when the problem data includes block-circulant matrices as is the case in the analysis of uncertain mechanical structures with spatial symmetry.     

Effect of sintering temperature on dielectric properties, vibrational modes and crystal structures of Ba[(Ni0.7Zn0.3)1/3Nb2/3]O3 ceramics

The Ba[(Ni_0.7Zn_0.3)_1/3Nb_2/3]O₃ solid solutions were sintered at 1450, 1500, and 1550 °C for 3 h, respectively, by conventional solid-state sintering method, so as to clarify the effect of the sintering temperatures on vibrational modes, crystal structures, and dielectric properties. Ceramics were characterized by X-ray diffraction (XRD), Raman spectroscopy and Fourier transform far-infrared reflection (FTIR) spectroscopy. Space group and crystal symmetry of Pm[`3]m Pm\bar{3}m were determined by XRD. Lattice vibrational spectra, obtained by Raman and FTIR spectroscopy, show the correlation among polar phonon modes, crystal structures, and dielectric properties of Ba[(Ni_0.7Zn_0.3)_1/3Nb_2/3]O₃ ceramics as a function of the sintering temperatures. The results demonstrate that the dielectric constant e_r \varepsilon_{r} reaches a maximum value of 35.713 at 1500 °C and is related to Raman shifts of the A_1g(O) modes and the FWHM values of the E_g(O) modes, the temperature coefficient of the capacitance t_c \tau_{c} , which gradually increases from −6 × 10⁻⁶/°C to 0, is closely related to the Raman shifts of E_g(O) modes, and the dielectric loss values are closely connected with the full width at half-maximum of E_g(O) active modes and the Raman shifts of of the A_1g(O) modes with the increasing temperatures. FTIR shows that the dielectric properties are closely related to the far-infrared phonon modes. Raman and FTIR active modes were indicated according to the group theory.     

The dual variable method for finite element discretizations of Navier/Stokes equations

The numerical solution of two-dimensional, transient, incompressible Navier–Stokes problems is considered. The dual variable method, originally developed in the context of a finite difference discretization, is a technique to considerably reduce the size of the linear system to be solved at each time step. The steps involved in the method are (1) the determination of the rank of the discrete divergence operator, A, (2) the determination of a basis for the null space of A, N(A), and (3) the calculation of a particular solution of the discrete continuity equation. A finite element implementation of the method is presented using quadrilateral piecewise bilinear velocity/constant pressure elements. Algorithms for the determination of a basis for N(A) and a particular solution are presented. Numerical comparisons of primitive versus dual variable formulations on several problems demonstrate the advantage of the dual variable method, in terms of both execution speed and memory requirements.