More Like this

1. High-precision quantum algorithms for partial differential equations

   https://doi.org/10.22331/q-2021-11-10-574  

   Childs, Andrew M.; Liu, Jin-Peng; Ostrander, Aaron (November 2021, Quantum)

   Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations. 

   more » « less
2. Enhanced alternating energy minimization methods for stochastic galerkin matrix equations

   https://doi.org/10.1007/s10543-021-00903-x  

   Lee, Kookjin; Elman, Howard C.; Powell, Catherine E.; Lee, Dongeun (January 2022, BIT numerical mathematics)

   In uncertainty quantification, it is commonly required to solve a forward model consisting of a partial differential equation (PDE) with a spatially varying uncertain coefficient that is represented as an affine function of a set of random variables, or parameters. Discretizing such models using stochastic Galerkin finite element methods (SGFEMs) leads to very high-dimensional discrete problems that can be cast as linear multi-term matrix equations (LMTMEs). We develop efficient computational methods for approximating solutions of such matrix equations in low rank. To do this, we follow an alternating energy minimization (AEM) framework, wherein the solution is represented as a product of two matrices, and approximations to each component are sought by solving certain minimization problems repeatedly. Inspired by proper generalized decomposition methods, the iterative solution algorithms we present are based on a rank-adaptive variant of AEM methods that successively computes a rank-one solution component at each step. We introduce and evaluate new enhancement procedures to improve the accuracy of the approximations these algorithms deliver. The efficiency and accuracy of the enhanced AEM methods is demonstrated through numerical experiments with LMTMEs associated with SGFEM discretizations of parameterized linear elliptic PDEs. 

   more » « less
3. On Some Quasi-Variational Inequalities and Other Problems with Moving Sets

   Menaldi, José-Luis; Rautenberg, Carlos N. (January 2021, Journal of convex analysis)

   null (Ed.)

   Since its introduction over 50 years ago, the concept of Mosco convergence has permeated through diverse areas of mathematics and applied sciences. These include applied analysis, the theory of partial differential equations, numerical analysis, and infinite dimensional constrained optimization, among others. In this paper we explore some of the consequences of Mosco convergence on applied problems that involve moving sets, with some historical accounts, and modern trends and features. In particular, we focus on connections with density of convex intersections, finite element approximations, quasi-variational inequalities, and impulse problems. 

   more » « less
4. Efficient quantum algorithm for dissipative nonlinear differential equations

   https://doi.org/10.1073/pnas.2026805118  

   Liu, Jin-Peng; Kolden, Herman Øie; Krovi, Hari K.; Loureiro, Nuno F.; Trivisa, Konstantina; Childs, Andrew M. (August 2021, Proceedings of the National Academy of Sciences)

   null (Ed.)

   Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming R < 1 , where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity T 2 q   poly ( log ⁡ T , log ⁡ n , log ⁡ 1 / ϵ ) / ϵ , where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R ≥ 2 . Finally, we discuss potential applications, showing that the R < 1 condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R. 

   more » « less
5. Finite element approximation of steady flows of colloidal solutions

   https://doi.org/10.1051/m2an/2021043  

   Bonito, Andrea; Girault, Vivette; Guignard, Diane; Rajagopal, Kumbakonam R.; Süli, Endre (September 2021, ESAIM: Mathematical Modelling and Numerical Analysis)

   We consider the mathematical analysis and numerical approximation of a system of nonlinear partial differential equations that arises in models that have relevance to steady isochoric flows of colloidal suspensions. The symmetric velocity gradient is assumed to be a monotone nonlinear function of the deviatoric part of the Cauchy stress tensor. We prove the existence of a weak solution to the problem, and under the additional assumption that the nonlinearity involved in the constitutive relation is Lipschitz continuous we also prove uniqueness of the weak solution. We then construct mixed finite element approximations of the system using both conforming and nonconforming finite element spaces. For both of these we prove the convergence of the method to the unique weak solution of the problem, and in the case of the conforming method we provide a bound on the error between the analytical solution and its finite element approximation in terms of the best approximation error from the finite element spaces. We propose first a Lions–Mercier type iterative method and next a classical fixed-point algorithm to solve the finite-dimensional problems resulting from the finite element discretisation of the system of nonlinear partial differential equations under consideration and present numerical experiments that illustrate the practical performance of the proposed numerical method. 

   more » « less