A Fast Preconditioned Iterative Algorithm for the Electromagnetic Scattering from a Large Cavity

In this paper, a fast preconditioned Krylov subspace iterative algorithm is proposed for the electromagnetic scattering from a rectangular large open cavity embedded in an infinite ground plane. The scattering problem is described by the Helmholtz equation with a nonlocal artificial boundary condition on the aperture of the cavity and Dirichlet boundary conditions on the walls of the cavity. Compact fourth order finite difference schemes are employed to discretize the bounded domain problem. A much smaller interface discrete system is reduced by introducing the discrete Fourier transformation in the horizontal and a Gaussian elimination in the vertical direction, presented in Bao and Sun (SIAM J. Sci. Comput. 27:553, 2005). An effective preconditioner is developed for the Krylov subspace iterative solver to solve this interface system. Numerical results demonstrate the remarkable efficiency and accuracy of the proposed method.     

On the orthogonal similarity transformation (OST)-based sensitivity analysis method for robust topology optimization under loading uncertainty: a mathematical proof and its extension

The main purpose of this work is to provide a mathematical proof of our previously proposed orthogonal similarity transformation (OST)-based sensitivity analysis method (Zhao et al. Struct Multidisc Optim 50(3):517–522 2014a, Comput Methods Appl Mech Engrg 273:204–218 c); the proof is designed to show the method’s computational effectiveness. Theoretical study of computational efficiency for both robust topology optimization and robust concurrent topology optimization problems shows the necessity of the OST-based sensitivity analysis method for practical problems. Numerical studies were conducted to demonstrate the computational accuracy of the OST-based sensitivity analysis method and its efficiency over the conventional method. The research leads us to conclude that the OST-based sensitivity analysis method can bring considerable computational savings when used for large-scale robust topology optimization problems, as well as robust concurrent topology optimization problems.     

An iteration method for solving the linear system Ax=b

In this paper, based on a convergence splitting of the matrix $A$, we present an inner–outer iteration method for solving the linear system $Ax=b$. We analyze the overall convergence of this method without any other restriction on its parameters. Moreover, we give the accelerated inner–outer iteration method, and discuss how to apply the inner–outer iterations as a preconditioner for the Krylov subspace methods. The inner–outer iteration method can also be used for the solution of $AXB=C$. Finally, several numerical examples are given to validate the performance of our proposed algorithms.     

Fast Iterative Method with a Second-Order Implicit Difference Scheme for Time-Space Fractional Convection–Diffusion Equation

In this paper we intend to establish fast numerical approaches to solve a class of initial-boundary problem of time-space fractional convection–diffusion equations. We present a new unconditionally stable implicit difference method, which is derived from the weighted and shifted Grünwald formula, and converges with the second-order accuracy in both time and space variables. Then, we show that the discretizations lead to Toeplitz-like systems of linear equations that can be efficiently solved by Krylov subspace solvers with suitable circulant preconditioners. Each time level of these methods reduces the memory requirement of the proposed implicit difference scheme from \({\mathcal {O}}(N^2)\) to \({\mathcal {O}}(N)\) and the computational complexity from \({\mathcal {O}}(N^3)\) to \({\mathcal {O}}(N\log N)\) in each iterative step, where N is the number of grid nodes. Extensive numerical examples are reported to support our theoretical findings and show the utility of these methods over traditional direct solvers of the implicit difference method, in terms of computational cost and memory requirements.     

Method of Lines Transpose: An Efficient Unconditionally Stable Solver for Wave Propagation

Building upon recent results obtained in Causley and Christlieb (SIAM J Numer Anal 52(1):220–235, 2014), Causley et al. (Math Comput 83(290):2763–2786, 2014, Method of lines transpose: high order L-stable O(N) schemes for parabolic equations using successive convolution, 2015), we describe an efficient second-order, unconditionally stable scheme for solving the wave equation, based on the method of lines transpose (MOL\(^T\)), and the resulting semi-discrete (i.e. continuous in space) boundary value problem. In Causley and Christlieb (SIAM J Numer Anal 52(1):220–235, 2014), unconditionally stable schemes of high order were derived, and in Causley et al. (Method of lines transpose: high order L-stable O(N) schemes for parabolic equations using successive convolution, 2015) a high order, fast \(\mathcal {O}(N)\) spatial solver was derived, which is matrix-free and is based on dimensional-splitting. In this work, are interested in building a wave solver, and our main concern is the development of boundary conditions. We demonstrate all desired boundary conditions for a wave solver, including outflow boundary conditions, in 1D and 2D. The scheme works in a logically Cartesian fashion, and the boundary points are embedded into the regular mesh, without incurring stability restrictions, so that boundary conditions are imposed without any reduction in the order of accuracy. We demonstrate how the embedded boundary approach works in the cases of Dirichlet and Neumann boundary conditions. Further, we develop outflow and periodic boundary conditions for the MOL\(^T\) formulation. Our solver is designed to couple with particle codes, and so special attention is also paid to the implementation of point sources, and soft sources which can be used to launch waves into waveguides.     

An \mathcal O (N \log N) Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices

This article describes a fast direct solver (i.e., not iterative) for partial hierarchically semi-separable systems. This solver requires a storage of $\mathcal O (N \log N)$ and has a computational complexity of $\mathcal O (N \log N)$ arithmetic operations. The numerical benchmarks presented illustrate the method in the context of interpolation using radial basis functions. The key ingredients behind this fast solver are recursion, efficient low rank factorization using Chebyshev interpolation, and the Sherman–Morrison–Woodbury formula. The algorithm and the analysis are worked out in detail. The performance of the algorithm is illustrated for a variety of radial basis functions and target accuracies.     

An efficient second-order SQP method for structural topology optimization

This article presents a Sequential Quadratic Programming (SQP) solver for structural topology optimization problems named TopSQP. The implementation is based on the general SQP method proposed in Morales et al. J Numer Anal 32(2):553–579 (2010) called SQP+. The topology optimization problem is modelled using a density approach and thus, is classified as a nonconvex problem. More specifically, the SQP method is designed for the classical minimum compliance problem with a constraint on the volume of the structure. The sub-problems are defined using second-order information. They are reformulated using the specific mathematical properties of the problem to significantly improve the efficiency of the solver. The performance of the TopSQP solver is compared to the special-purpose structural optimization method, the Globally Convergent Method of Moving Asymptotes (GCMMA) and the two general nonlinear solvers IPOPT and SNOPT. Numerical experiments on a large set of benchmark problems show good performance of TopSQP in terms of number of function evaluations. In addition, the use of second-order information helps to decrease the objective function value.     

Efficient use of iterative solvers in nested topology optimization

In the nested approach to structural optimization, most of the computational effort is invested in the solution of the analysis equations. In this study, it is suggested to reduce this computational cost by using an approximation to the solution of the analysis problem, generated by a Krylov subspace iterative solver. By choosing convergence criteria for the iterative solver that are strongly related to the optimization objective and to the design sensitivities, it is possible to terminate the iterative solution of the nested equations earlier compared to traditional convergence measures. The approximation is computationally shown to be sufficiently accurate for the purpose of optimization though the nested equation system is not necessarily solved accurately. The approach is tested on several large-scale topology optimization problems, including minimum compliance problems and compliant mechanism design problems. The optimized designs are practically identical while the time spent on the analysis is reduced significantly.     

Fast Iterative Adaptive Multi-quadric Radial Basis Function Method for Edges Detection of Piecewise Functions—I: Uniform Mesh

In Jung et al. (Appl Numer Math 61:77–91, 2011), an iterative adaptive multi-quadric radial basis function (IAMQ-RBF) method has been developed for edges detection of the piecewise analytical functions. For a uniformly spaced mesh, the perturbed Toeplitz matrices, which are modified by those columns where the shape parameters are reset to zero due to the appearance of edges at the corresponding locations, are created. Its inverse must be recomputed at each iterative step, which incurs a heavy \(O(n^3)\) computational cost. To overcome this issue of efficiency, we develop a fast direct solver (IAMQ-RBF-Fast) to reformulate the perturbed Toeplitz system into two Toeplitz systems and a small linear system via the Sherman–Morrison–Woodbury formula. The \(O(n^2)\) Levinson–Durbin recursive algorithm that employed Yule–Walker algorithm is used to find the inverse of the Toeplitz matrix fast. Several classical benchmark examples show that the IAMQ-RBF-Fast based edges detection method can be at least three times faster than the original IAMQ-RBF based one. And it can capture an edge with fewer grid points than the multi-resolution analysis (Harten in J Comput Phys 49:357–393, 1983) and just as good as if not better than the L1PA method (Denker and Gelb in SIAM J Sci Comput 39(2):A559–A592, 2017). Preliminary results in the density solution of the 1D Mach 3 extended shock–density wave interaction problem solved by the hybrid compact-WENO finite difference scheme with the IAMQ-RBF-Fast based shocks detection method demonstrating an excellent performance in term of speed and accuracy, are also shown.     

Distributed control and constraint preconditioners

Optimization problems with constraints that involve a partial differential equation arise widely in many areas of the sciences and engineering, in particular in problems of design. The solution of such PDE-constrained optimization problems is usually a major computational task. Here we consider simple problems of this type: distributed control problems in which the 2- and 3-dimensional Poisson problem is the PDE. Large dimensional linear systems result from the discretization and need to be solved: these systems are of saddle-point type. We introduce an optimal preconditioner for these systems that leads to convergence of symmetric Krylov subspace iterative methods in a number of iterations which does not increase with the dimension of the discrete problem. These preconditioners are block structured and involve standard multigrid cycles. The optimality of the preconditioned iterative solver is proved theoretically and verified computationally in several test cases. The theoretical proof indicates that these approaches may have much broader applicability for other partial differential equations.     

Efficient Solvers of Discontinuous Galerkin Discretization for the Cahn–Hilliard Equations

In this paper, we develop and analyze a fast solver for the system of algebraic equations arising from the local discontinuous Galerkin (LDG) discretization and implicit time marching methods to the Cahn–Hilliard (CH) equations with constant and degenerate mobility. Explicit time marching methods for the CH equation will require severe time step restriction $(\varDelta t \sim O(\varDelta x^4))$ , so implicit methods are used to remove time step restriction. Implicit methods will result in large system of algebraic equations and a fast solver is essential. The multigrid (MG) method is used to solve the algebraic equations efficiently. The Local Mode Analysis method is used to analyze the convergence behavior of the linear MG method. The discrete energy stability for the CH equations with a special homogeneous free energy density $\Psi (u)=\frac{1}{4}(1-u^2)^2$ is proved based on the convex splitting method. We show that the number of iterations is independent of the problem size. Numerical results for one-dimensional, two-dimensional and three-dimensional cases are given to illustrate the efficiency of the methods. We numerically show the optimal complexity of the MG solver for $\mathcal{P }^1$ element. For $\mathcal{P }^2$ approximation, the optimal or sub-optimal complexity of the MG solver are numerically shown.     

Improving topology optimization intuition through games

This paper describes the educational game, TopOpt Game, which invites the player to solve various optimization challenges. The main purpose of gamifying topology optimization is to create a supplemental educational tool which can be used to introduce concepts of topology optimization to newcomers as well as to train human intuition of topology optimization. The players are challenged to solve the standard minimum compliance problem in 2D by distributing material in a design domain given a number of loads and supports with a material constraint. A statistical analysis of the gameplay data shows that players achieve higher scores the more they play the game. The game is freely available for the iOS platform at Apple’s App Store and at http://www.topopt.dtu.dk/?q=node/909 for Windows and OSX.     

Supercloseness of Continuous Interior Penalty Methods on Shishkin Triangular Meshes and Hybrid Meshes for Singularly Perturbed Problems with Characteristic Layers

A fast preconditioned penalty method is developed for a system of parabolic linear complementarity problems (LCPs) involving tempered fractional order partial derivatives governing the price of American options whose underlying asset follows a geometry Lévy process with multi-state regime switching. By means of the penalty method, the system of LCPs is approximated with a penalty term by a system of nonlinear tempered fractional partial differential equations (TFPDEs) coupled by a finite-state Markov chain. The system of nonlinear TFPDEs is discretized with the shifted Grünwald approximation by an upwind finite difference scheme which is shown to be unconditionally stable. Semi-smooth Newton’s method is utilized to solve the finite difference scheme as an outer iterative method in which the Jacobi matrix is found to possess Toeplitz-plus-diagonal structure. Consequently, the resulting linear system can be fast solved by the Krylov subspace method as an inner iterative method via fast Fourier transform (FFT). Furthermore, a novel preconditioner is proposed to speed up the convergence rate of the inner Krylov subspace iteration with theoretical analysis. With the above-mentioned preconditioning technique via FFT, under some mild conditions, the operation cost in each Newton’s step can be expected to be \(\mathcal{O}(N\mathrm{log}N)\), where N is the size of the coefficient matrix. Numerical examples are given to demonstrate the accuracy and efficiency of our proposed fast preconditioned penalty method.     

A Fast Discontinuous Galerkin Method for a Bond-Based Linear Peridynamic Model Discretized on a Locally Refined Composite Mesh

We develop a family of fast discontinuous Galerkin (DG) finite element methods for a bond-based linear peridynamic (PD) model in one space dimension. More precisely, we develop a preconditioned fast piecewise-constant DG scheme on a geometrically graded locally refined composite mesh which is suited for the scenario in which the jump discontinuity of the displacement field occurs at the one of the nodes in the original uniform partition. We also develop a preconditioned fast piecewise-linear DG scheme on a uniform mesh that has a second-order convergence rate when the jump discontinuity occurs at one of the computational nodes or has a convergence rate of one-half order otherwise. Motivated by these results, we develop a preconditioned fast hybrid DG scheme that is discretized on a locally uniformly refined composite mesh to numerically simulate the PD model where the jump discontinuity of the displacement field occurs inside a computational cell. We use a piecewise-constant DG scheme on a uniform mesh and a piecewise-linear DG scheme on a locally uniformly refined mesh of mesh size \(O(h^2)\), which has an overall convergence rate of O(h). Because of their nonlocal nature, numerical methods for PD models generate dense stiffness matrices which have \(O(N^2)\) memory requirement and \(O(N^3)\) computational complexity, where N is the number of computational nodes. In this paper, we explore the structure of the stiffness matrices to develop three preconditioned fast Krylov subspace iterative solvers for the DG method. Consequently, the methods have significantly reduced computational complexity and memory requirement. Numerical results show the utility of the numerical methods.     

On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes

We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.     

Robust Solvers for Inverse Imaging Problems Using Dense Single-Precision Hardware

We present an iterative framework for robustly solving large inverse problems arising in imaging using only single-precision (or other reduced-precision) arithmetic, which allows the use of high-density processors (e.g. Cell BE and Graphics Processing Units). Robustness here means linear-convergence even for large problems (billions of variables), with high levels of noise (signal-to-noise levels less than unity). This framework handles problems formulated as quadratic and general non-linear minimization problems. Sparse and dense problems can be treated, as long as there are efficient parallelizable matrix-vector products for the transformations involved. Outer iterations correspond to approximate solutions of a quadratic minimization problem, using a single Newton step. Inner iterations correspond to the estimation of the step via truncated Neumann series or minimax polynomial approximations built from operator splittings. Given the convergence analysis, this approach can also be used in embedded environments with fixed computation budgets, or certification requirements, like real-time medical imaging. We describe a benchmark problem from MRI, and a series of penalty functions suited to this framework. An important family of such penalties is motivated by both bilateral filtering and total variation, and we show how they can be optimized using linear programming. We also discuss penalties designed to segment images, and use different types of a priori knowledge, and show numerically that the different penalties are effective when used in combination.