Jacob K. White

Richard Y. Zhang, Jacob K. White

We consider the sequence acceleration problem for the alternating direction method-of-multipliers (ADMM) applied to a class of equality-constrained problems with strongly convex quadratic objectives, which frequently arise as the Newton subproblem of interior-point methods. Within this context, the ADMM update equations are linear, the iterates are confined within a Krylov subspace, and the General Minimum RESidual (GMRES) algorithm is optimal in its ability to accelerate convergence. The basic ADMM method solves a $κ$-conditioned problem in $O(\sqrtκ)$ iterations. We give theoretical justification and numerical evidence that the GMRES-accelerated variant consistently solves the same problem in $O(κ^{1/4})$ iterations for an order-of-magnitude reduction in iterations, despite a worst-case bound of $O(\sqrtκ)$ iterations. The method is shown to be competitive against standard preconditioned Krylov subspace methods for saddle-point problems. The method is embedded within SeDuMi, a popular open-source solver for conic optimization written in MATLAB, and used to solve many large-scale semidefinite programs with error that decreases like $O(1/k^{2})$, instead of $O(1/k)$, where $k$ is the iteration index.

M. T. Homer Reid, Steven G. Johnson, Jacob K. White

We present a generic technique, automated by computer-algebra systems and available as open-source software \cite{scuff-em}, for efficient numerical evaluation of a large family of singular and nonsingular 4-dimensional integrals over triangle-product domains, such as those arising in the boundary-element method (BEM) of computational electromagnetism. To date, practical implementation of BEM solvers has often required the aggregation of multiple disparate integral-evaluation schemes to treat all of the distinct types of integrals needed for a given BEM formulation; in contrast, our technique allows many different types of integrals to be handled by the \emph{same} algorithm and the same code implementation. Our method is a significant generalization of the Taylor--Duffy approach \cite{Taylor2003,Duffy1982}, which was originally presented for just a single type of integrand; in addition to generalizing this technique to a broad class of integrands, we also achieve a significant improvement in its efficiency by showing how the \emph{dimension} of the final numerical integral may often be reduced by one. In particular, if $n$ is the number of common vertices between the two triangles, in many cases we can reduce the dimension of the integral from $4-n$ to $3-n$, obtaining a closed-form analytical result for $n=3$ (the common-triangle case).

Samuel P. Groth, Athanasios G. Polimeridis, Alexandra Tambova et al.

Recently, the volume integral equation (VIE) approach has been proposed as an efficient simulation tool for silicon photonics applications [J. Lightw. Technol. 36, 3765 (2018)]. However, for the high-frequency and strong contrast problems arising in photonics, the convergence of iterative solvers for the solution of the linear system can be extremely slow. The uniform discretization of the volume integral operator leads to a three-level Toeplitz matrix, which is well suited to preconditioning via its circulant approximation. In this paper, we describe an effective circulant preconditioning strategy based on the multi-level circulant preconditioner of Chan and Olkin [Numer. Algorithms 6, 89 (1994)]. We show that this approach proves ideal in the canonical photonics problem of propagation within a uniform waveguide, in which the flow is unidirectional. For more complex photonics structures, such as Bragg gratings, directional couplers, and disk resonators, we generalize our preconditioning strategy via geometrical partitioning (leading to a block-diagonal circulant preconditioner) and homogenization (for inhomogeneous structures). Finally, we introduce a novel memory reduction technique enabling the preconditioner's memory footprint to remain manageable, even for extremely long structures. The range of numerical results we present demonstrates that the preconditioned VIE is fast and has great utility for the numerical exploration of prototype photonics devices.