The relationship amongst coefficient matrices in symmetric Galerkin BEM for 2D elastic problems

Based on the assumption that solutions from different methods are the same, the relationship amongst weakly singular, strongly singular and hypersingular matrices associated with symmetric Galerkin BEM is derived for 2D elastic problems. Hypersingularity is avoided through matrix manipulations so that only weakly and strongly singularities need to be solved. Compared with the advantages brought about by symmetry, the additional computation caused by matrix manipulations is not so important in many cases, especially for time domain dynamic problems or when one wants to couple BEM with other symmetric schemes. Both static and dynamic problems have been studied, and three numerical examples are included to show the effectiveness and accuracy of the present formulation.     

The Boundary Element Method with a Fast Multipole Accelerated Integration Technique for 3D Elastostatic Problems with Arbitrary Body Forces

A line integration boundary element method (LIBEM) is proposed for three-dimensional elastostatic problems with body forces. The method is a boundary-only discretization method like the traditional boundary element method (BEM), and the boundary elements created in BEM can be used directly in the proposed method for constructing the integral lines. Finally, the body forces are computed by summing one-dimensional integrals on straight lines. Background cells can be used to cut the lines into sub-lines to compute the integrals more easily and efficiently. To further reduce the computational time of LIBEM, the fast multipole method is applied to accelerate the method for large-scale computations and the details of the fast multipole line integration method for 3D elastostatic problems are given. Numerical examples are presented to demonstrate the accuracy and efficiency of the proposed method.     

Analytical integral algorithm applied to boundary layer effect and thin body effect in BEM for anisotropic potential problems

A new completely analytical integral algorithm is proposed and applied to the evaluation of nearly singular integrals in boundary element method (BEM) for two-dimensional anisotropic potential problems. The boundary layer effect and thin body effect are dealt with. The completely analytical integral formulas are suitable for the linear and non-isoparametric quadratic elements. The present algorithm applies the analytical formulas to treat nearly singular integrals. The potentials and fluxes at the interior points very close to boundary are evaluated. The unknown potentials and fluxes at boundary nodes for thin body problems with the thickness-to-length ratios from 1E−1 to 1E−8 are accurately calculated by the present algorithm. Numerical examples on heat conduction demonstrate that the present algorithm can effectively handle nearly singular integrals occurring in boundary layer effect and thin body effect in BEM. Furthermore, the present linear BEM is especially accurate and efficient for the numerical analysis of thin body problems.     

3-D time domain BEM analysis with animated graphics

The intense computational requirements of a time domain solution of 3-D elastodynamic problems based on the boundary element method (BEM) have limited its implementation to main frame computers. In this work a simplified 3-D direct time domain BEM is described along with a 3-D interactive animated graphics code custom made to accompany the above BEM analysis. The simplifications introduced make its use efficient and accurate even in a microcomputer environment. Representative numerical results from the dynamic interaction of a rigid square machine foundation with an elastic half space are presented.     

A MLPG(LBIE) approach in combination with BEM

The local boundary integral equation (LBIE) approach is a promising meshless method, recently proposed as an effective alternative to the boundary element method (BEM), for solving non-homogeneous, anisotropic and non-linear problems. Since the LBIE method utilizes in its weak form fundamental solutions as test functions, it can be considered as one of the six meshless local Petrov–Galerkin (MLPG) methods proposed by Atluri and coworkers. This explains the use of the initials MLPG(LBIE) in the title of the present paper. This work addresses a coupling of a new MLPG(LBIE) method, recently proposed by the authors for elastodynamic problems, and the BEM. Because both methods conclude to a final system of linear equations expressed in terms of nodal displacement and tractions, their combination is accomplished directly with no further transformations as it happens in other MLPG/BEM formulations as well as in typical hybrid finite element method/BEM schemes. The coupling approach is demonstrated for static and frequency domain elastodynamic problems. Three representative examples are provided in order to illustrate the achieved accuracy of the proposed here MLPG(LBIE)/BE methodology.     

Multi-period Vehicle Routing Problem with Due dates

In this paper we study the Multi-period Vehicle Routing Problem with Due dates (MVRPD), where customers have to be served between a release and a due date. Customers with due dates exceeding the planning period may be postponed at a cost. A fleet of capacitated vehicles is available to perform the distribution in each day of the planning period. The objective of the problem is to find vehicle routes for each day such that the overall cost of the distribution, including transportation costs, inventory costs and penalty costs for postponed service, is minimized. We present alternative formulations for the MVRPD and enhance the formulations with valid inequalities. The formulations are solved with a branch-and-cut algorithm and computationally compared. Furthermore, we present a computational analysis aimed at highlighting managerial insights. We study the potential benefit that can be achieved by incorporating flexibility in the due dates and the number of vehicles. Finally, we highlight the effect of reducing vehicle capacity.     

Combined asymptotic finite-element modeling of thin layers for scalar elliptic problems

Thin layers with material properties which differ significantly from those of the adjacent media appear in a variety of applications, as in the form of fiber coatings in composite materials. Fully modeling of such thin layers by standard finite element (FE) analysis is often associated with difficult meshing and high computational cost. Asymptotic procedures which model such thin domains by an interface of no thickness on which appropriate interface conditions are devised have been known in the literature for some time. The present paper shows how the first-order asymptotic interface model proposed by Bövik in 1994, and later generalized by Benveniste, can be incorporated in a FE formulation, to yield an accurate and efficient computational scheme for problems involving thin layers. This is done here for linear scalar elliptic problems in two dimensions, prototyped by steady-state heat conduction. Moreover, it is shown that by somewhat modifying the formulation of the Bövik–Benveniste asymptotic model, the proposed formulation is made to preserve the self-adjointness of the original three-phase problem, thus leading to a symmetric FE stiffness matrix. Numerical examples are presented that demonstrate the performance of the method, and show that the proposed scheme is more cost-effective than the full standard FE modeling of the layer.     

Boundary element analysis of capped and uncapped pile groups

A conventional application of the Boundary Element Method (BEM) to the elastic analysis of sizeable capped pile groups rapidly leads to large computational execution time. This paper develops a BEM formulation for solving such problems more efficiently, and with adequate precision, in which the traction along each pile in a group is represented by a polynomial function. With this approach the tractions need only a few nodes along the shaft to be represented and all the integrals involved can be analytically evaluated. The pile is supposed to be rigid but the formulation can be easily extended to the inclusion of its flexibility. Only vertical displacement compatibility between the soil, the piles and the smooth, rigid cap is enforced. The cap–soil interface is divided into triangular elements, each with three nodes, across which contact pressures vary linearly. Numerical results are presented for single piles and for pile groups, with and without ground-contacting caps. In all these examples the pile loads and group stiffnesses are close to those obtained from other formulations.     

A boundary element formulation for the substation grounding design

A Boundary Element approach for the numerical computation of substation grounding systems is presented. In this general formulation, several widespread intuitive methods (such as Average Potential Method (APM)) can be identified as the result of specific choices for the test and trial functions and suitable assumptions introduced in the Boundary Element Method (BEM) formulation to reduce computational cost. While linear and parabolic leakage current elements allow to increase accuracy, computing time is drastically reduced by means of new completely analytical integration techniques and semi-iterative methods for solving linear equations systems. This BEM formulation has been implemented in a specific Computer Aided Design system for grounding analysis developed in the last years. The feasibility of this new approach is demonstrated with its application to a real problem.     

Topological derivatives applied to fluid flow channel design optimization problems

Topology optimization methods application for viscous flow problems is currently an active area of research. A general approach to deal with shape and topology optimization design is based on the topological derivative. This relatively new concept represents the first term of the asymptotic expansion of a given shape functional with respect to the small parameter which measures the size of singular domain perturbations, such as holes and inclusions. In previous topological derivative-based formulations for viscous fluid flow problems, the topology is obtained by nucleating and removing holes in the fluid domain which creates numerical difficulties to deal with the boundary conditions for these holes. Thus, we propose a topological derivative formulation for fluid flow channel design based on the concept of traditional topology optimization formulations in which solid or fluid material is distributed at each point of the domain to optimize the cost function subjected to some constraints. By using this idea, the problem of dealing with the hole boundary conditions during the optimization process is solved because the asymptotic expansion is performed with respect to the nucleation of inclusions – which mimic solid or fluid phases – instead of inserting or removing holes in the fluid domain, which allows for working in a fixed computational domain. To evaluate the formulation, an optimization problem which consists in minimizing the energy dissipation in fluid flow channels is implemented. Results from considering Stokes and Navier-Stokes are presented and compared, as well as two- (2D) and three-dimensional (3D) designs. The topologies can be obtained in a few iterations with well defined boundaries.     

On a pair of job-machine assignment problems with two stages

We consider two assignment problems in which a number of jobs are assigned to the same number of machines that operate in parallel, but in two stages. They are known as the ‘2-stage time minimizing assignment problem’ and the ‘bi-level time minimizing assignment problem’. These problems have the following characteristics in common:

• Each of the machines processes one job (non-preemptively, without help of other machines).

• The job-machine assignments are partitioned into two successive stages of parallel processing.

• The objective is to minimize the makespan, the sum of the primary and the secondary completion time.

Both problems can be solved by (a series of) assignment problems. We improve the related computational complexities by applying reoptimization. Under some conditions a quadratic complexity is derived.We introduce a parameter weighing the relative importance of the primary and the secondary cost per time unit. The parametric problems can be solved, for all parameter values simultaneously, within the same reduced time complexity bounds.

Scope and purpose

As it is often important to solve problems quickly, it is essential to reduce the computational complexity of available algorithms, as far as possible. We consider two problems which arise when parallel scheduling is done in two successive stages; they can be tackled by solving a series of linear assignment problems. We show that they can be solved more efficiently, using properties of the classical linear assignment problem.In practice, the cost per time unit in the two stages need not be equal. A parameter controlling the ratio between these costs defines a parametric version of each problem. The algorithms of reduced time complexity can be extended to these parametric problem versions.     

Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods

The Bundle Method and the Volume Algorithm are among the most efficient techniques to obtain accurate Lagrangian dual bounds for hard combinatorial optimization problems. We propose here to compare their performance on very large scale Fixed‐Charge Multicommodity Capacitated Network Design problems. The motivation is not only the quality of the approximation of these bounds as a function of the computational time but also the ability to produce feasible primal solutions and thus to reduce the gap for very large instances for which optimal solutions are out of reach. Feasible solutions are obtained through the use of Lagrangian information in constructive and improving heuristic schemes. We show in particular that, if the Bundle implementation has provided great quality bounds in fewer iterations, the Volume Algorithm is able to reduce the gaps of the largest instances, taking profit of the low computational cost per iteration compared to the Bundle Method.     

Efficient blind dereverberation and echo cancellation based on independent component analysis for actual acoustic signals

This letter presents a new algorithm for blind dereverberation and echo cancellation based on independent component analysis (ICA) for actual acoustic signals. We focus on frequency domain ICA (FD-ICA) because its computational cost and speed of learning convergence are sufficiently reasonable for practical applications such as hands-free speech recognition. In applying conventional FD-ICA as a preprocessing of automatic speech recognition in noisy environments, one of the most critical problems is how to cope with reverberations. To extract a clean signal from the reverberant observation, we model the separation process in the short-time Fourier transform domain and apply the multiple input/output inverse-filtering theorem (MINT) to the FD-ICA separation model. A naive implementation of this method is computationally expensive, because its time complexity is the second order of reverberation time. Therefore, the main issue in dereverberation is to reduce the high computational cost of ICA. In this letter, we reduce the computational complexity to the linear order of the reverberation time by using two techniques: (1) a separation model based on the independence of delayed observed signals with MINT and (2) spatial sphering for preprocessing. Experiments show that the computational cost grows in proportion to the linear order of the reverberation time and that our method improves the word correctness of automatic speech recognition by 10 to 20 points in a RT??= 670 ms reverberant environment.     

Aligning block permutation methods for topology transformation on computational grids

Many traditional parallel matrix computing algorithms are performed on regular resource topologies, such as mesh. However, the grid resource topology is often irregular in practice. In this paper, we present a transformation algorithm of grid resource topology for achieving virtual meshes. And on the virtual mesh, these traditional parallel algorithms can be performed in a modern computational grid environment. The basic idea of our topology transformation is to align the basic blocks of grid computational resources through permutations in a virtual mesh. Designing a cost function of heuristic search scheme for the transformation, we use it to fully exploit the computational and communicational abilities of grid resources. The experiment results show that our aligning block permutation can significantly reduce the time complexity of search tree. They also show that the heuristic search scheme can effectively find the block permutation that makes better use of computational and communicational abilities of grid resources.     

Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation

We consider vehicle routing and crew scheduling problems that involve a lexicographic bi-level objective function (for instance, minimizing first the number of vehicles and second the operational costs) and can be solved by column generation where the subproblem is a resource constrained shortest path problem. Such problems are often modeled using a single-level objective function with a large fixed cost (weight) for ensuring the minimization of the primary objective. In this paper, we study the impact on the solution time of the fixed cost value. First, we present computational results which show that the solution time increases as the fixed cost value gets larger. Then, we develop an exact dynamic fixed cost procedure compatible with column generation that starts with a relatively small fixed cost value and increases it iteratively until optimality is reached. To prove optimality, a shortest path problem with resource constraints needs to be solved. Through a series of computational experiments on two types of problems, we show that this procedure can reduce solution times by up to 50% when compared to an approach relying on one very large fixed cost value.     

极点配置广义稳态Kalman估值器

应用时域上的现代时间序列分析方法,基于自回归滑动平均(ARMA)新息模型和白噪 声估值器,应用控制理论中的极点配置原理,对线性离散时间广义随机系统提出了极点配置广义 稳态Kalman估值器.它们具有全局渐近稳定性,且通过配置估值器的极点可按指数衰减速率使 初始状态估值的影响快速消失.它们可在统一框架下处理滤波、平滑和预报问题.它们避免了Riccati 方程和最优初始状态估值的计算,因而可减小计算负担.一个仿真例子说明了它们的有效性.     

STBC-OFDM系统中有效降低计算量的盲接收机

为了降低空时分组码-正交频分复用（STBC-OFDM）系统中盲多用户接收机的计算复杂度,将基于子空间的接收机应用到STBC-OFDM系统中,证明其可以有效地降低计算复杂度并加快收敛速度。在此基础上,利用STBC码的正交特性推导出了两个权值之间的关系式,使得计算复杂度又降低了一半。仿真结果表明所提出的盲多用户接收机能剔除常规接收机中的冗余度,在误码率不变的前提下有效地解决了常规接收机中计算量大的问题。     

Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems

Mixed integer programming (MIP) formulations for scheduling problems can be classified based on the decision variables upon which they rely. In this paper, four different MIP formulations based on four different types of decision variables are presented for various parallel machine scheduling problems. The goal of this research is to identify promising optimization formulation paradigms that can subsequently be used to either (1) solve larger practical scheduling problems of interest to optimality and/or (2) be used to establish tighter lower solution bounds for those under study. We present the computational results and discuss formulation efficacy for total weighted completion time and maximum completion time problems for the identical parallel machine case.     

A FEM–BEM coupling method for a nonlinear transmission problem modelling Coulomb friction contact

A nonlinear transmission problem modelling elastoplastic interface problems with contact and Coulomb friction is reduced to a boundary/domain variational inequality. We present a corresponding FEM/BEM coupling procedure and derive for its Galerkin solution an a priori error estimate. Furthermore we reformulate the problem as an equivalent saddle point problem whose discretization can be solved by the Uzawa algorithm. Convergence of the FEM/BEM coupling method is proved and numerical results are given.     

Applications of anisotropic one‐step leapfrog HIE‐FDTD method in microwave circuit and antenna

To verify the effect of artificial anisotropy parameters in one‐step leapfrog hybrid implicit‐explicit finite‐difference time‐domain (FDTD) method, we calculated several microwave components with different characteristics. Introduced auxiliary field variable can reduce the program difficulty and improve the computational efficiency without additional computational time and memory cost. Analyses of the numerical results are proved that the calculation time is reduced to about one‐sixth compared to the traditional FDTD method for the same example simulated. The memory cost and relative error are remained at a good level. The numerical experiments for microwave circuit and antenna have been well demonstrated the method available.