Combinatorial optimization with interaction costs: Complexity and solvable cases

We introduce and study the combinatorial optimization problem with interaction costs (COPIC). COPIC is the problem of finding two combinatorial structures, one from each of two given families, such that the sum of their independent linear costs and the interaction costs between elements of the two selected structures is minimized. COPIC generalizes the quadratic assignment problem and many other well studied combinatorial optimization problems, and hence covers many real world applications. We show how various topics from different areas in the literature can be formulated as special cases of COPIC. The main contributions of this paper are results on the computational complexity and approximability of COPIC for different families of combinatorial structures (e.g. spanning trees, paths, matroids), and special structures of the interaction costs. More specifically, we analyze the complexity if the interaction cost matrix is parameterized by its rank and if it is a diagonal matrix. Also, we determine the structure of the intersection cost matrix, such that COPIC is equivalent to independently solving linear optimization problems for the two given families of combinatorial structures.     

An iterative implementation of the Uzawa algorithm for 3-D fluid flow problems

A new iterative algorithm for the solution of the three-dimensional Navier–Stokes equations by the finite element method is presented. This algorithm is based on a combination of the Uzawa and the Arrow–Hurwicz algorithms and uses a preconditioning technique to enhance convergence. Numerical tests are presented for the cubic cavity problem with two elements, namely the linear brick Q₁?P₀ and the enriched linear brick Q₁⁺ ? P₁. It is shown that the proposed methodology is optimal with the enriched element and that the CPU time varies as NEQ^1·44, where NEQ is the number of equations.     

Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations

Time harmonic Maxwell equations in lossless media lead to a second order differential equation for the electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec spaces can be employed to get approximate solutions numerically. The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically, two overlapping Schwarz methods will be shown to yield uniform preconditioners.

     

Fast Iterative Solution of Saddle Point Problems in Optimal Control Based on Wavelets

In this paper, wavelet techniques are employed for the fast numerical solution of a control problem governed by an elliptic boundary value problem with boundary control. A quadratic cost functional involving natural norms of the state and the control is to be minimized. Firstly the constraint, the elliptic boundary value problem, is formulated in an appropriate weak form that allows to handle varying boundary conditions explicitly: the boundary conditions are treated by Lagrange multipliers, leading to a saddle point problem. This is combined with a fictitious domain approach in order to cover also more complicated boundaries.Deviating from standard approaches, we then use (biorthogonal) wavelets to derive an equivalent infinite discretized control problem which involves only ₂-norms and -operators. Classical methods from optimization yield the corresponding optimality conditions in terms of two weakly coupled (still infinite) saddle point problems for which a unique solution exists. For deriving finite-dimensional systems which are uniformly invertible, stability of the discretizations has to be ensured. This together with the ₂-setting circumvents the problem of preconditioning: all operators have uniformly bounded condition numbers independent of the discretization.In order to numerically solve the resulting (finite-dimensional) linear system of the weakly coupled saddle point problems, a fully iterative method is proposed which can be viewed as an inexact gradient scheme. It consists of a gradient algorithm as an outer iteration which alternatingly picks the two saddle point problems, and an inner iteration to solve each of the saddle point problems, exemplified in terms of the Uzawa algorithm. It is proved here that this strategy converges, provided that the inner systems are solved sufficiently well. Moreover, since the system matrix is well-conditioned, it is shown that in combination with a nested iteration strategy this iteration is asymptotically optimal in the sense that it provides the solution on discretization level J with an overall amount of arithmetic operations that is proportional to the number of unknows N _J on that level.Finally, numerical results are provided.     

Parametric active aeroelastic control of a morphing wing using the receptance method

This study proposes the parametric active aeroelastic control of a folding wing, which is a promising concept of morphing wings, by integrating the parameterized aeroservoelastic model and the receptance-based control strategy. It starts with establishing the parameterized aeroservoelastic model of the folding wing with respect to its folding angle and air speed. The transfer functions between the embedded sensors and the actuators of the folding wing are then efficiently obtained using the parameterized aeroservoelastic model. Finally, control gains for varying folding angle and air speed of the wing are synthesized using the receptance method. The results of numerical analyses show that smooth evolutions of the control gains can be obtained over a wide range of folding angles and air speeds, although the dynamic behavior of the folding wing is sensitive to these parameters. In addition, the active aeroelastic control can effectively suppress aeroelastic vibrations and expand flutter boundaries of the folding wing. The benefit of the parametric active aeroelastic control for the folding wing, i.e., smoothly switching among the control laws without exciting undesirable vibrations is highlighted.     

混凝土细观力学分析程序中的快速算法与并行算法设计

针对一套混凝土细观力学分析程序,在分析其计算方法与计算效率的不足之后,提出了采用稀疏矩阵与稀疏向量技术来高效实现有限元刚度矩阵装配过程的算法,并采用双门槛不完全Cholesky分解预条件技术与CG法相结合来高效地求解稀疏线性方程组。之后,从整体上提出了一个将有限单元分布与未知量分布有机结合的并行算法设计方案,并分别针对刚度矩阵装配、双门槛不完全Cholesky分解、稀疏矩阵与稠密向量相乘、稀疏向量相加等核心算法,进行了相应的并行算法设计。最后,在由每节点2 CPU的8个Intel Xeon节点采用千兆以太网连成的机群上,针对两个混凝土数值试样进行了数值实验,第一个试样含44117个网格点与53200个有限单元,第二个试样含71013个网格点与78800个有限单元;对第一个试样,原串行程序进行全程567次加载计算需要984.83小时约41天,采用文中串行算法后,模拟时间减少到22531秒约6.26小时,采用并行算法在16个CPU上的模拟时间进一步降为3860秒约1.07小时。对第二个试样,原串行程序进行全程94次加载计算需要467.19小时约19.5天,采用文中串行算法后,模拟时间减少到11453秒约3.18小时,采用并行算法在16个CPU上的模拟时间进一步降为1704秒约28.4分钟。串行算法的改进与并行算法的设计大大缩短了计算时间,对加快混凝土力学性能的分析研究具有重要意义。     

A Multilevel AINV Preconditioner

In this paper we describe an algebraic multilevel extension of the approximate inverse AINV preconditioner for solving symmetric positive definite linear systems Ax=b with the preconditioned conjugate gradient method. The smoother is the approximate inverse M and the coarse grids and the interpolation operator are constructed by looking at the entries of M. Numerical examples are given for problems arising from discretization of partial differential equations.     

Comparison of the GMRES and ORTHOMIN for the black oil model in porous media

This paper deals with the application of the GMRES algorithm to a three‐dimensional, three‐phase black oil model used in petroleum reservoir simulation. Comparisons between the GMRES and ORTHOMIN algorithms in terms of storage and total flops per restart step are given. Numerical results show that the GMRES is faster than the ORTHOMIN for large‐scale simulation problems. The GMRES uses only as much as 63% of the CPU time of the ORTHOMIN for some of the problems tested. Copyright © 2005 John Wiley & Sons, Ltd.     

鞍点问题基于半增广的松弛分裂预条件子

对于(1,1)块为正定的鞍点问题,本文给出了半增广松弛分裂预条件子.文中分析了预条件矩阵特征值分布情况,并用数值实验验证了半增广松弛分裂预条件子的有效性.