A preconditioned GMRES for complex dense linear systems from electromagnetic wave scattering problems

We consider the numerical solution of linear systems arising from the discretization of the electric field integral equation (EFIE). For some geometries the associated matrix can be poorly conditioned making the use of a preconditioner mandatory to obtain convergence. The electromagnetic scattering problem is here solved by means of a preconditioned GMRES in the context of the multilevel fast multipole method (MLFMM). The novelty of this work is the construction of an approximate hierarchically semiseparable (HSS) representation of the near-field matrix, the part of the matrix capturing interactions among nearby groups in the MLFMM, as preconditioner for the GMRES iterations. As experience shows, the efficiency of an ILU preconditioning for such systems essentially depends on a sufficient fill-in, which apparently sacrifices the sparsity of the near-field matrix. In the light of this experience we propose a multilevel near-field matrix and its corresponding HSS representation as a hierarchical preconditioner in order to substantially reduce the number of iterations in the solution of the resulting system of equations.     

Semidefinite relaxations for non-convex quadratic mixed-integer programming

We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as a bounding routine in an SDP-based branch-and-bound framework. In case of a convex objective function, the new SDP bound improves the bound given by the continuous relaxation of the problem. Numerical experiments show that our algorithm performs well on various types of non-convex instances.     

Resilience of perfect matchings and Hamiltonicity in random graph processes

Let {G_i} be the random graph process: starting with an empty graph G₀ with n vertices, in every step i ≥ 1 the graph G_i is formed by taking an edge chosen uniformly at random among the nonexisting ones and adding it to the graph G_{i ? 1}. The classical “hitting‐time” result of Ajtai, Komlós, and Szemerédi, and independently Bollobás, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches 2, that is if δ(G_i) ≥ 2 then G_i is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for edges, the 2‐core of the graph G_m remains Hamiltonian even after an adversary removes ‐fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings.     

On induced matchings

Let q^*(G) denote the minimum integer t for which E(G) can be partitioned into t induced matchings of G. Faudree et al. conjectured that q^*(G)d², if G is a bipartite graph and d is the maximum degree of G. In this note, we give an affirmative answer for d=3, the first nontrivial case of this conjecture.     

Analysis of Calving Events in Antarctic Ice Shelves Using Configurational Forces

Previous studies on the sensitivity of cracks in ice shelves with different boundary conditions, stress states and density profiles revealed the need for further analyses. As the transfer of boundary conditions from dynamic ice flow simulations to the linear elastic fracture analyses proved to be a critical point in previous studies, a new approach to relate viscous and elastic material behaviour is proposed. The numerical simulations are conducted using Finite Elements utilizing the concept of configurational forces. To show the applicability of the approach, a 2-dimensional plane stress geometry with volume loads due to the ice shelf flow is analyzed. The resulting crack path is compared to available crack paths from satellite images. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)