Search

The B-series composition theorem has been an important topic in numerical analysis of ordinary differential equations for the past-half century. Traditional proofs of this theorem rely on labelled trees, whereas recent developments in B-series analysis favour the use of unlabelled trees. In this paper, we present a new proof of the B-series composition theorem that does not depend on labelled trees. A key challenge in this approach is accurately counting combinations related to ``pruning.'' This challenge is overcome by introducing the concept of ``assignment.''

Nesterov's acceleration in continuous optimization can be understood in a novel way when Nesterov's accelerated gradient (NAG) method is considered as a linear multistep (LM) method for gradient flow. Although the NAG method for strongly convex functions (NAG-sc) has been fully discussed, the NAG method for $L$-smooth convex functions (NAG-c) has not. To fill this gap, we show that the existing NAG-c method can be interpreted as a variable step size LM (VLM) for the gradient flow. Surprisingly, the VLM allows linearly increasing step sizes, which explains the acceleration in the convex case. Here, we introduce a novel technique for analyzing the absolute stability of VLMs. Subsequently, we prove that NAG-c is optimal in a certain natural class of VLMs. Finally, we construct a new broader class of VLMs by optimizing the parameters in the VLM for ill-conditioned problems. According to numerical experiments, the proposed method outperforms the NAG-c method in ill-conditioned cases. These results imply that the numerical analysis perspective of the NAG is a promising working environment, and considering a broader class of VLMs could further reveal novel methods.

We propose a new unified framework for describing and designing gradient-based convex optimization methods from a numerical analysis perspective. There the key is the new concept of weak discrete gradients (weak DGs), which is a generalization of DGs standard in numerical analysis. Via weak DG, we consider abstract optimization methods, and prove unified convergence rate estimates that hold independent of the choice of weak DGs except for some constants in the final estimate. With some choices of weak DGs, we can reproduce many popular existing methods, such as the steepest descent and Nesterov's accelerated gradient method, and also some recent variants from numerical analysis community. By considering new weak DGs, we can easily explore new theoretically-guaranteed optimization methods; we show some examples. We believe this work is the first attempt to fully integrate research branches in optimization and numerical analysis areas, so far independently developed.

Some continuous optimization methods can be connected to ordinary differential equations (ODEs) by taking continuous limits, and their convergence rates can be explained by the ODEs. However, since such ODEs can achieve any convergence rate by time scaling, the correspondence is not as straightforward as usually expected, and deriving new methods through ODEs is not quite direct. In this letter, we pay attention to stability restriction in discretizing ODEs and show that acceleration by time scaling basically implies deceleration in discretization; they balance out so that we can define an attainable unique convergence rate which we call an "essential convergence rate".

In this paper, we propose linearly implicit and arbitrary high-order conservative numerical schemes for ordinary differential equations with a quadratic invariant. Many differential equations have invariants, and numerical schemes for preserving them have been extensively studied. Since linear invariants can be easily kept after discretisation, quadratic invariants are essentially the simplest ones. Quadratic invariants are important objects that appear not only in many physical examples but also in the computationally efficient conservative schemes for general invariants such as scalar auxiliary variable approach, which have been studied in recent years. It is known that quadratic invariants can be kept relatively easily compared to general invariants, and indeed can be preserved by canonical Runge--Kutta methods. However, there is no unified method for constructing linearly implicit and high order conservative schemes. In this paper, we construct such schemes based on canonical Runge--Kutta methods and prove some properties involving accuracy.

This paper deals with the geometric numerical integration of gradient flow and its application to optimization. Gradient flows often appear as model equations of various physical phenomena, and their dissipation laws are essential. Therefore, dissipative numerical methods, which are numerical methods replicating the dissipation law, have been studied in the literature. Recently, Cheng, Liu, and Shen proposed a novel dissipative method, the Lagrange multiplier approach, for gradient flows, which is computationally cheaper than existing dissipative methods. Although their efficacy is numerically confirmed in existing studies, the existence results of the Lagrange multiplier approach are not known in the literature. In this paper, we establish some existence results. We prove the existence of the solution under a relatively mild assumption. In addition, by restricting ourselves to a special case, we show some existence and uniqueness results with concrete bounds. As gradient flows also appear in optimization, we further apply the latter results to optimization problems.

In this paper, we present a novel investigation of the so-called SAV approach, which is a framework to construct linearly implicit geometric numerical integrators for partial differential equations with variational structure. SAV approach was originally proposed for the gradient flows that have lower-bounded nonlinear potentials such as the Allen-Cahn and Cahn-Hilliard equations, and this assumption on the energy was essential. In this paper, we propose a novel approach to address gradient flows with unbounded energy such as the KdV equation by a decomposition of energy functionals. Further, we will show that the equation of the SAV approach, which is a system of equations with scalar auxiliary variables, is expressed as another gradient system that inherits the variational structure of the original system. This expression allows us to construct novel higher-order integrators by a certain class of Runge-Kutta methods. We will propose second and fourth order schemes for conservative systems in our framework and present several numerical examples.

We review the EfficientQA competition from NeurIPS 2020. The competition focused on open-domain question answering (QA), where systems take natural language questions as input and return natural language answers. The aim of the competition was to build systems that can predict correct answers while also satisfying strict on-disk memory budgets. These memory budgets were designed to encourage contestants to explore the trade-off between storing retrieval corpora or the parameters of learned models. In this report, we describe the motivation and organization of the competition, review the best submissions, and analyze system predictions to inform a discussion of evaluation for open-domain QA., Comment: 26 pages; Published in Proceedings of Machine Learning Research (PMLR), NeurIPS 2020 Competition and Demonstration Track

Kahan's method and a two-step generalization of the discrete gradient method are both linearly implicit methods that can preserve a modified energy for Hamiltonian systems with a cubic Hamiltonian. These methods are here investigated and compared. The schemes are applied to the Korteweg-de Vries equation and the Camassa-Holm equation, and the numerical results are presented and analysed., Comment: 18 pages, 11 figures, 33 subfigures. Submitted to Journal of Computational and Applied Mathematics, proceedings for NUMDIFF-15

In this paper, we consider the use of discrete gradients for differential-algebraic equations (DAEs) with a conservation/dissipation law. As one of the most popular numerical methods for conservative/dissipative ordinary differential equations, the framework of discrete gradient methods has been intensively developed over recent decades. Although discrete gradients have been applied to several specific conservative/dissipative DAEs, no unified framework for DAEs has yet been constructed. In this paper, we move toward the establishment of such a framework, and introduce concepts including an appropriate linear gradient structure for DAEs. Then, we reveal that the simple use of discrete gradients does not imply the discrete conservation/dissipation laws. Fortunately, however, we can successfully construct a new discrete gradient method for the case of index-1 DAEs. We believe this first attempt provides an indispensable basis for constructing a unified framework of discrete gradient methods for DAEs.

The modified Hunter--Saxton equation models the propagation of short capillary-gravity waves. As it involves a mixed derivative, its initial value problem on the periodic domain is much more complicated than the standard evolutionary equations. Although its local well-posedness has recently been proved, the behavior of its solution is yet to be investigated. In this paper, to develop a reliable numerical method for this problem, we derive a conservative finite difference scheme. Then, we rigorously prove not only its stability in the sense of the uniform norm but also its uniform convergence to sufficiently smooth exact solutions. Discrete conservation laws are used to overcome the difficulty due to the mixed derivative.

We consider problems to make a given bidirected graph strongly connected with minimum cardinality of additional signs or additional arcs. For the former problem, we show the minimum number of additional signs and give a linear-time algorithm for finding an optimal solution. For the latter problem, we give a linear-time algorithm for finding a feasible solution whose size is equal to the obvious lower bound or more than that by one., Comment: 14pages

Recently, various evolutionary partial differential equations (PDEs) with a mixed derivative have been emerged and drawn much attention. Nonetheless, their PDE-theoretical and numerical studies are still in their early stage. In this paper, we aim at the unified framework of numerical methods for such PDEs. However, due to the presence of the mixed derivative, we cannot discuss numerical methods without some appropriate reformulation, which is mathematically challenging itself. Therefore, we first propose a novel procedure for the reformulation of target PDEs into a standard form of evolutionary equations. This contribution may become an important basis not only of numerical analysis, but also of PDE-theory. In order to illustrate this point, we establish the global well-posedness of the sine-Gordon equation. After that, we classify and discuss the spatial discretizations based on the proposed reformulation technique. As a result, we show the average-difference method is suitable for the discretization of the mixed derivative.