A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems

Summary. We present a Lagrange multiplier based two-level domain decomposition method for solving iteratively large-scale systems of equations arising from the finite element discretization of high-frequency exterior Helmholtz problems. The proposed method is essentially an extension of the regularized FETI (Finite Element Tearing and Interconnecting) method to indefinite problems. Its two key ingredients are the regularization of each subdomain matrix by a complex interface lumped mass matrix, and the preconditioning of the interface problem by an auxiliary coarse problem constructed to enforce at each iteration the orthogonality of the residual to a set of carefully chosen planar waves. We show numerically that the proposed method is scalable with respect to the mesh size, the subdomain size, and the wavenumber. We report performance results for a submarine application that highlight the efficiency of the proposed method for the solution of high frequency acoustic scattering problems discretized by finite elements. Received March 17, 1998 / Revised version received June 7, 1999 / Published online January 27, 2000     

A note on some computationally difficult set covering problems

Fulkerson et al. have given two examples of set covering problems that are empirically difficult to solve. They arise from Steiner triple systems and the larger problem, which has a constraint matrix of size 330 × 45 has only recently been solved. In this note, we show that the Steiner triple systems do indeed give rise to a series of problems that are probably hard to solve by implicit enumeration. The main result is that for ann variable problem, branch and bound algorithms using a linear programming relaxation, and/or elimination by dominance require the examination of a super-polynomial number of partial solutionsThis paper was written while the author was a CORE Fellow at the Université de Louvain, Louvain-la-Neuve, Belgium.     

Incomplete block factorization preconditioning for indefinite elliptic problems

Summary. The application of the finite difference method to approximate the solution of an indefinite elliptic problem produces a linear system whose coefficient matrix is block tridiagonal and symmetric indefinite. Such a linear system can be solved efficiently by a conjugate residual method, particularly when combined with a good preconditioner. We show that specific incomplete block factorization exists for the indefinite matrix if the mesh size is reasonably small, and that this factorization can serve as an efficient preconditioner. Some efforts are made to estimate the eigenvalues of the preconditioned matrix. Numerical results are also given. Received November 21, 1995 / Revised version received February 2, 1998 / Published online July 28, 1999     

Discrete and continuous coupled nonlinear integrable systems via the dressing method

A discrete analog of the dressing method is presented and used to derive integrable nonlinear evolution equations, including two infinite families of novel continuous and discrete coupled integrable systems of equations of nonlinear Schrödinger type. First, a demonstration is given of how discrete nonlinear integrable equations can be derived starting from their linear counterparts. Then, starting from two uncoupled, discrete one‐directional linear wave equations, an appropriate matrix Riemann‐Hilbert problem is constructed, and a discrete matrix nonlinear Schrödinger system of equations is derived, together with its Lax pair. The corresponding compatible vector reductions admitted by these systems are also discussed, as well as their continuum limits. Finally, by increasing the size of the problem, three‐component discrete and continuous integrable discrete systems are derived, as well as their generalizations to systems with an arbitrary number of components.     

D-optimal matrices via quadratic integer optimization

We show how to express the problem of searching for D-optimal matrices as a Linear and Quadratic Integer Optimization problem. We also focus our attention in the case where the size of the circulant submatrices that are used to construct a D-optimal matrix is a multiple of 3. In this particular case, we describe some additional combinatorial and number-theoretic characteristics that a solution of the D-optimal matrix problem must possess. We give some solutions for some quite challenging D-optimal matrix problems that can be used as benchmarks to test the efficiency of Linear and Quadratic Integer Optimization algorithms.     

An analysis of finite element locking in a parameter dependent model problem

Summary. We consider the bilinear finite element approximation of smooth solutions to a simple parameter dependent elliptic model problem, the problem of highly anisotropic heat conduction. We show that under favorable circumstances that depend on both the finite element mesh and on the type of boundary conditions, the effect of parametric locking of the standard FEM can be reduced by a simple variational crime. In our analysis we split the error in two orthogonal components, the approximation error and the consistency error, and obtain different bounds for these separate components. Also some numerical results are shown. Received September 6, 1999 / Revised version received March 28, 2000 / Published online April 5, 2001     

The problem of membrane locking in finite element analysis of cylindrical shells

Summary We analyse the problem of membrane locking in (h, p) finite element models of a thin hemicylindrical shell roof loaded by a smoothly varying normal pressure distribution. We show that in the standard finite element method, locking occurs especially at low values ofp and when the finite element grid is not aligned with the axis of the cylinder. A general strategy of avoiding locking by using modified bilinear forms is introduced, and a special implementation of this strategy on aligned rectangular grids is considered.     

Consensus of second-order discrete-time multi-agent systems with fixed topology

This paper studies the consensus of second-order discrete-time multi-agent systems with fixed topology. First, we formulate the problem and give some preliminaries. Then, by algebraic graph theory and matrix theory, the convergence of system matrix is analyzed. Our main results indicate that the consensus of second-order system can be achieved if and only if the topology graph has a directed spanning tree and the values of the scaling parameters satisfy a range. The eigenvalues of the corresponding Laplacian matrix play a key role in reaching consensus. Finally, numerical simulations are given to illustrate the results.     

Convexity Properties Associated with Nonconvex Quadratic Matrix Functions and Applications to Quadratic Programming

We establish several convexity results which are concerned with nonconvex quadratic matrix (QM) functions: strong duality of quadratic matrix programming problems, convexity of the image of mappings comprised of several QM functions and existence of a corresponding S-lemma. As a consequence of our results, we prove that a class of quadratic problems involving several functions with similar matrix terms has a zero duality gap. We present applications to robust optimization, to solution of linear systems immune to implementation errors and to the problem of computing the Chebyshev center of an intersection of balls. This research was partially supported by the Israel Science Foundation under Grant ISF 489/06.     

Analysis of pairwise comparison matrices: an empirical research

Pairwise comparison (PC) matrices are used in multi-attribute decision problems (MADM) in order to express the preferences of the decision maker. Our research focused on testing various characteristics of PC matrices. In a controlled experiment with university students (N=227) we have obtained 454 PC matrices. The cases have been divided into 18 subgroups according to the key factors to be analyzed. Our team conducted experiments with matrices of different size given from different types of MADM problems. Additionally, the matrix elements have been obtained by different questioning procedures differing in the order of the questions. Results are organized to answer five research questions. Three of them are directly connected to the inconsistency of a PC matrix. Various types of inconsistency indices have been applied. We have found that the type of the problem and the size of the matrix had impact on the inconsistency of the PC matrix. However, we have not found any impact of the questioning order. Incomplete PC matrices played an important role in our research. The decision makers behavioral consistency was as well analyzed in case of incomplete matrices using indicators measuring the deviation from the final order of alternatives and from the final score vector.     

A note on conjugate gradient convergence – Part III

Summary. In this paper we again consider the rate of convergence of the conjugate gradient method. We start with a general analysis of the conjugate gradient method for uniformly bounded solutions vectors and matrices whose eigenvalues are uniformly bounded and positive. We show that in such cases a fixed finite number of iterations of the method gives some fixed amount of improvement as the the size of the matrix tends to infinity. Then we specialize to the finite element (or finite difference) scheme for the problem . We show that for some classes of function we see this same effect. For other functions we show that the gain made by performing a fixed number of iterations of the method tends to zero as the size of the matrix tends to infinity. Received July 9, 1998 / Published online March 16, 2000     

Locking in finite-element approximations to long thin extensible beams

Finite-element approximations to a linearized model of the extensiblebeam problem are examined. For long thin beams, the model maybe viewed as a fourth-order singular perturbation problem. Ifthe mesh size in the finite-element method is not taken to befine enough, the numerical solution may exhibit locking; weexplore the cause of this phenomenon and a possible correction.     

Estimation of exponential convergence rate and exponential stability for neural networks with time-varying delay

We study the problem of estimating the exponential convergence rate and exponential stability for neural networks with time-varying delay. Some criteria for exponential stability are derived by using the linear matrix inequality (LMI) approach. They are less conservative than the existing ones. Some analytical methods are employed to investigate the bounds on the interconnection matrix and activation functions so that the systems are exponentially stable.     

Numerical stability for a dynamic Naghdi shell

We consider an elastic model for a shell incorporating shear, membrane, bending and dynamic effects. We make use of the theory proposed by Arnold and Brezzi [1] based on a locking free non-standard mixed variational formulation. This method is implemented in terms of the displacement and rotation variables as the minimization of an altered energy functional. We extend this theory to the shell vibrations problem and establish optimal error estimates independent of the thickness, thereby proving that shear and membrane locking is avoided. We study the numerical stability both in static and dynamic regimes. The approximation schemes are tested on specific examples and the numerical results confirm the estimates obtained from theory.     

Symmetry preserving partial eigenvalue assignment for undamped structural systems

In this paper, the partial eigenvalue assignment problem for undamped structural systems by output feedback control where the output matrix is also a designing parameter is considered. We propose a method to solve this problem in which the unwanted eigenvalues are move to desired values and all other eigenpairs remain unchanged. In addition, our method can preserve symmetry of the systems. Numerical example shows that the proposed method is effective.     

Breather resonant phase locking by an external perturbation

We study the effect of the resonant phase locking in the problem of the sine-Gordon equation breather under the action of a small oscillating external force with slowly varying frequency. We obtain equations determining the time evolution of the parameters of the perturbed breather. We describe the regular asymptotic procedure of averaging such equations and show that the averaged equations in the leading order already well describe the phenomenon of resonant phase locking in which the breather oscillations are strongly excited. We obtain necessary and sucient conditions for the phase locking relating the rate of the perturbation frequency variation and its amplitude to the initial data of the breather. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 152, No. 2, pp. 356–367, August, 2007.     

Throughput-oriented channel assignment for opportunistic spectrum access networks

Cognitive radio (CR) is a revolutionary technology in wireless communications that enhances spectrum utilization by allowing opportunistic and dynamic spectrum access. One of the key challenges in this domain is how CR users cooperate to dynamically access the available spectrum opportunities in order to maximize the overall perceived throughput. In this paper, we consider the coordinated spectrum access problem in a multi-user single-transceiver CR network (CRN), where each CR user is equipped with only one half-duplex transceiver. We first formulate the dynamic spectrum access as a rate/power control and channel assignment optimization problem. Our objective is to maximize the sum-rate achieved by all contending CR users over all available spectrum opportunities under interference and hardware constraints. We first show that this problem can be formulated as a mixed integer nonlinear programming (MINLP) problem that is NP-hard, in general. By exploiting the fact that actual communication systems have a finite number of available channels, each with a given maximum transmission power, we transfer this MINLP into a binary linear programming problem (BLP). Due to its integrality nature, this BLP is expected to be NP-hard. However, we show that its constraint matrix satisfies the total unimodularity property, and hence our problem can be optimally solved in polynomial time using linear programming (LP). To execute the optimal assignment in a distributed manner, we then present a distributed CSMA/CA-based random access mechanism for CRNs. We compare the performance of our proposed mechanism with reference CSMA/CA channel access mechanisms designed for CRNs. Simulation results show that our proposed mechanism significantly improves the overall network throughput and preserves fairness.     

Locking effects in the finite element approximation of elasticity problems

Summary We consider the finite element approximation of the 2D elasticity problem when the Poisson ratiov is close to 0.5. It is well-known that the performance of certain commonly used finite elements deteriorates asv0, a phenomenon calledlocking. We analyze this phenomenon and characterize the strength of the locking androbustness of varioush-version schemes using triangular and rectangular elements. We prove that thep-andh-p versions are free of locking with respect to the error in the energy norm. A generalization of our theory to the 3D problem is also discussed.The work of this author was supported in part by the Office of Naval Research under Naval Research Grant N00014-90-J-1030The work of this author was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, U.S. Air Force, under grant AFOSR 89-0252     

On order‐reducible sinc discretizations and block‐diagonal preconditioning methods for linear third‐order ordinary differential equations

By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd.