The Experts below are selected from a list of 15582 Experts worldwide ranked by ideXlab platform
Nicholas J Higham - One of the best experts on this subject based on the ideXlab platform.
-
a new approach to probabilistic rounding Error analysis
SIAM Journal on Scientific Computing, 2019Co-Authors: Nicholas J Higham, Theo MaryAbstract:Traditional rounding Error analysis in numerical linear algebra leads to Backward Error bounds involving the constant $\gamma^{}_n = nu/(1-nu)$, for a problem size $n$ and unit roundoff $u$. In lig...
-
improved inverse scaling and squaring algorithms for the matrix logarithm
SIAM Journal on Scientific Computing, 2012Co-Authors: Awad H Almohy, Nicholas J HighamAbstract:A popular method for computing the matrix logarithm is the inverse scaling and squaring method, which essentially carries out the steps of the scaling and squaring method for the matrix exponential in reverse order. Here we make several improvements to the method, putting its development on a par with our recent version [\emph{SIAM J. Matrix Anal.\ Appl.}, 31 (2009), pp.\ 970--989] of the scaling and squaring method for the exponential. In particular, we introduce Backward Error analysis to replace the previous forward Error analysis; obtain Backward Error bounds in terms of the quantities $\|A^p\|^{1/p}$, for several small integer $p$, instead of $\|A\|$; and use special techniques to compute the argument of the Pad\'e approximant more accurately. We derive one algorithm that employs a Schur decomposition, and thereby works with triangular matrices, and another that requires only matrix multiplications and the solution of multiple right-hand side linear systems. Numerical experiments show the new algorithms to be generally faster and more accurate than their existing counterparts and suggest that the Schur-based method is the method of choice for computing the matrix logarithm.
-
LARGE GROWTH FACrORS IN GAUSSIAN ELIMINATION WITH PIVOTING*
2012Co-Authors: Nicholas J Higham, Desmond J. Higham, Mims Eprint, J. HighamAbstract:Abstract. The growth factor plays an important role in the Error analysis of Gaussian elimination. It is well known that when partial pivoting or complete pivoting is used the growth factor is usually small, but it can be large. The examples of large growth usually quoted involve contrived matrices that are unlikely to occur in practice. We present real and complex n n matrices arising from practical applications that, for any pivoting strategy, yield growth factors bounded below by n/2 and n, respectively. These matrices enable us to improve the known lower bounds on the largest possible growth factor in the case of complete pivoting. For partial pivoting, we classify the set of real matrices for which the growth factor is 2 "-1 Finally, we show that large element growth does not necessarily lead to a large Backward Error in the solution of a particular linear system, and we comment on the practical implications of this result. Key words. Gaussian elimination, growth factor, partial pivoting, complete pivoting, Backward Error analysis, stability AMS(MOS) subject classifications, primary 65F05, 65G0
-
stability of householder qr factorization for weighted least squares problems
2010Co-Authors: Anthony J Cox, Nicholas J HighamAbstract:For least squares problems in which the rows of the coefficient matrix vary widely in norm, Householder QR factorization (without pivoting) has unsatisfactory Backward stability properties. Powell and Reid showed in 1969 that the use of both row and column pivoting leads to a desirable row-wise Backward Error result. We give a reworked Backward Error analysis in modern notation and prove two new results. First, sorting the rows by decreasing ∞-norm at the start of the factorization obviates the need for row pivoting. Second, row-wise Backward stability is obtained for only one of the two possible choices of sign in the Householder vector.
-
solving a quadratic matrix equation by newton s method with exact line searches
SIAM Journal on Matrix Analysis and Applications, 2001Co-Authors: Nicholas J HighamAbstract:We show how to incorporate exact line searches into Newton's method for solving the quadratic matrix equation AX2 + BX + C = 0, where A, B and C are square matrices. The line searches are relatively inexpensive and improve the global convergence properties of Newton's method in theory and in practice. We also derive a condition number for the problem and show how to compute the Backward Error of an approximate solution.
Ernst Hairer - One of the best experts on this subject based on the ideXlab platform.
-
geometric numerical integration structure preserving algorithms for ordinary differential equations
2009Co-Authors: Ernst Hairer, Christian Lubich, Gerhard WannerAbstract:Examples and Numerical Experiments.- Numerical Integrators.- Order Conditions, Trees and B-Series.- Conservation of First Integrals and Methods on Manifolds.- Symmetric Integration and Reversibility.- Symplectic Integration of Hamiltonian Systems.- Non-Canonical Hamiltonian Systems.- Structure-Preserving Implementation.- Backward Error Analysis and Structure Preservation.- Hamiltonian Perturbation Theory and Symplectic Integrators.- Reversible Perturbation Theory and Symmetric Integrators.- Dissipatively Perturbed Hamiltonian and Reversible Systems.- Oscillatory Differential Equations with Constant High Frequencies.- Oscillatory Differential Equations with Varying High Frequencies.- Dynamics of Multistep Methods.
-
conservation of energy momentum and actions in numerical discretizations of non linear wave equations
Numerische Mathematik, 2008Co-Authors: David Cohen, Ernst Hairer, Christian LubichAbstract:For classes of symplectic and symmetric time-stepping methods— trigonometric integrators and the Stormer–Verlet or leapfrog method—applied to spectral semi-discretizations of semilinear wave equations in a weakly non-linear setting, it is shown that energy, momentum, and all harmonic actions are approximately preserved over long times. For the case of interest where the CFL number is not a small parameter, such results are outside the reach of standard Backward Error analysis. Here, they are instead obtained via a modulated Fourier expansion in time.
-
geometric numerical integration structure preserving algorithms for ordinary differential equations
2004Co-Authors: Ernst Hairer, Christian Lubich, Gerhard WannerAbstract:Numerical methods that preserve properties of Hamiltonian systems, reversible systems, differential equations on manifolds and problems with highly oscillatory solutions are the subject of this book. A complete self-contained theory of symplectic and symmetric methods, which include Runge-Kutta, composition, splitting, multistep and various specially designed integrators, is presented and their construction and practical merits are discussed. The long-time behaviour of the numerical solutions is studied using a Backward Error analysis (modified equations) combined with KAM theory. The book is illustrated by many figures, it treats applications from physics and astronomy and contains many numerical experiments and comparisons of different approaches. The second edition is substantially revised and enlarged, with many improvements in the presentation and additions concerning in particular non-canonical Hamiltonian systems, highly oscillatory mechanical systems, and the dynamics of multistep methods.
-
long time energy conservation of numerical methods for oscillatory differential equations
SIAM Journal on Numerical Analysis, 2000Co-Authors: Ernst Hairer, Christian LubichAbstract:We consider second-order differential systems where high-frequency oscillations are generated by a linear part. We present a frequency expansion of the solution, and we discuss two invariants of the system that determine the coefficients of the frequency expansion. These invariants are related to the total energy and the oscillatory harmonic energy of the original system. For the numerical solution we study a class of symmetric methods that discretize the linear part without Error. We are interested in the case where the product of the step size with the highest frequency can be large. In the sense of Backward Error analysis we represent the numerical solution by a frequency expansion where the coefficients are the solution of a modified system. This allows us to prove the near-conservation of the total and the oscillatory energy over very long time intervals.
-
variable time step integration with symplectic methods
Applied Numerical Mathematics, 1997Co-Authors: Ernst HairerAbstract:Abstract Symplectic methods for Hamiltonian systems are known to have favorable properties concerning long-time integrations (no secular terms in the Error of the energy integral, linear Error growth in the angle variables instead of quadratic growth, correct qualitative behaviour) if they are applied with constant step sizes, while all of these properties are lost in a standard variable step size implementation. In this article we present a “meta-algorithm” which allows us to combine the use of variable steps with symplectic integrators, without destroying the above mentioned favorable properties. We theoretically justify the algorithm by a Backward Error analysis, and illustrate its performance by numerical experiments.
Mary Théo - One of the best experts on this subject based on the ideXlab platform.
-
Adversarial attacks via Backward Error analysis
HAL CCSD, 2021Co-Authors: Beuzeville Théo, Mary Théo, Boudier Pierre, Buttari Alfredo, Gratton Serge, Pralet StéphaneAbstract:Backward Error (BE) analysis was developed and popularized by James Wilkinson in the 1950s and 1960s, with origins in the works of Neumann and Goldstine (1947) and Turing (1948). It is a fundamental notion used in numerical linear algebra software, both as a theoretical and a practical tool for the rounding Error analysis of numerical algorithms. Broadly speaking the Backward Error quantifies, in terms of perturbation of input data, by how much the output of an algorithm fails to be equal to an expected quantity. For a given computed solution y, this amounts to computing the norm of the smallest perturbation ∆x of the input data x such that y is an exact solution of a perturbed system: f (x + ∆x) = y. Up to now, BE analysis has been applied to numerous linear algebra problems, always with the objective of quantifying the robustness of algebraic processes with respect to rounding Errors stemming from finite precision computations. While deep neural networks (DNN) have achieved an unprecedented success in numerous machine learning tasks in various domains, their robustness to adversarial attacks, rounding Errors, or quantization processes has raised considerable concerns from the machine learning community. In this work, we generalize BE analysis to DNN. This enables us to obtain closed formulas and a numerical algorithm for computing adversarial attacks. By construction, these attacks are optimal, and thereby smaller, in norm, than perturbations obtained with existing gradient-based approaches. We produce numerical results that support our theoretical findings and illustrate the relevance of our approach on well-known datasets
-
Sharper Probabilistic Backward Error Analysis for Basic Linear Algebra Kernels with Random Data
HAL CCSD, 2020Co-Authors: Higham Nicholas, Mary ThéoAbstract:Standard Backward Error analyses for numerical linear algebra algorithms provide worst-case bounds that can significantly overestimate the Backward Error. Our recent probabilistic Error analysis, which assumes rounding Errors to be independent random variables [SIAM J. Sci. Comput., 41 (2019), pp. A2815-A2835], contains smaller constants but its bounds can still be pessimistic. We perform a new probabilistic Error analysis that assumes both the data and the rounding Errors to be random variables and assumes only mean independence. We prove that for data with zero or small mean we can relax the existing probabilistic bounds of order \sqrt{n}u to much sharper bounds of order u, which are independent of n. Our fundamental result is for summation and we use it to derive results for inner products, matrix-vector products, and matrix-matrix products. The analysis answers the open question of why random data distributed on [-1,1] leads to smaller Error growth for these kernels than random data distributed on [0,1]. We also propose a new algorithm for multiplying two matrices that transforms the rows of the first matrix to have zero mean and we show that it can achieve significantly more accurate results than standard matrix multiplication
-
Stochastic Rounding and its Probabilistic Backward Error Analysis
2020Co-Authors: Connolly, Michael P., Higham, Nicholas J., Mary ThéoAbstract:Stochastic rounding rounds a real number to the next larger or smaller floating-point number with probabilities $1$ minus the relative distances to those numbers. It is gaining attention in deep learning because it can increase the success of low precision computations. We compare basic properties of stochastic rounding with those for round to nearest, finding properties in common as well as significant differences. We prove that for stochastic rounding the rounding Errors are mean independent random variables with zero mean. We derive a new version of our probabilistic Error analysis theorem from [{\em SIAM J. Sci. Comput.}, 41 (2019), pp.\ A2815--A2835], weakening the assumption of independence of the random variables to mean independence. These results imply that for a wide range of linear algebra computations the Backward Error for stochastic rounding is unconditionally bounded by a multiple of $\sqrt{n}\mkern1muu$ to first order, with a certain probability, where $n$ is the problem size and $u$ is the unit roundoff. This is the first scenario where the rule of thumb that one can replace $nu$ by $\sqrt{n}\mkern1muu$ in a rounding Error bound has been shown to hold without any additional assumptions on the rounding Errors. We also explain how stochastic rounding avoids the phenomenon of stagnation in sums, whereby small addends are obliterated by round to nearest when they are too small relative to the sum
-
Stochastic Rounding and its Probabilistic Backward Error Analysis
2020Co-Authors: Connolly, Michael P., Higham, Nicholas J., Mary ThéoAbstract:Stochastic rounding rounds a real number to the next larger or smaller floating-point number with probabilities $1$ minus the relative distances to those numbers. % It has a larger worst-case Error than round to nearest % but has useful statistical properties. It is gaining attention in deep learning because it can improve the accuracy of the computations. We compare basic properties of stochastic rounding with those for round to nearest, finding properties in common as well as significant differences. We prove that for stochastic rounding the rounding Errors are mean independent random variables with zero mean. We derive a new version of our probabilistic Error analysis theorem from [{\em SIAM J. Sci. Comput.}, 41 (2019), pp.\ A2815--A2835], weakening the assumption of independence of the random variables to mean independence. These results imply that for a wide range of linear algebra computations the Backward Error for stochastic rounding is unconditionally bounded by a multiple of $\sqrt{n}u$ to first order, with a certain probability, where $n$ is the problem size and $u$ is the unit roundoff. This is the first scenario where the rule of thumb that one can replace $nu$ by $\sqrt{n}u$ in a rounding Error bound has been shown to hold without any additional assumptions on the rounding Errors. We also explain how stochastic rounding avoids the phenomenon of stagnation in sums, whereby small addends are obliterated by round to nearest when they are too small relative to the sum
-
A New Approach to Probabilistic Rounding Error Analysis
'Society for Industrial & Applied Mathematics (SIAM)', 2019Co-Authors: Higham, Nicholas J., Mary ThéoAbstract:International audienceTraditional rounding Error analysis in numerical linear algebra leads to Backward Error bounds involving the constant γ n = nu/(1 − nu), for a problem size n and unit roundoff u. In the light of large-scale and possibly low-precision computations, such bounds can struggle to provide any useful information. We develop a new probabilistic rounding Error analysis that can be applied to a wide range of algorithms. By using a concentration inequality and making probabilistic assumptions about the rounding Errors, we show that in several core linear algebra computations γ n can be replaced by a relaxed constant γ n proportional to √ n log n u with a probability bounded below by a quantity independent of n. The new constant γ n grows much more slowly with n than γn. Our results have three key features: they are Backward Error bounds; they are exact, not first order; and they are valid for any n, unlike results obtained by applying the central limit theorem, which apply only as n → ∞. We provide numerical experiments that show that for both random and real-life matrices the bounds can be much smaller than the standard deterministic bounds and can have the correct asymptotic growth with n. We also identify two special situations in which the assumptions underlying the analysis are not valid and the bounds do not hold. Our analysis provides, for the first time, a rigorous foundation for the rule of thumb that "one can take the square root of an Error constant because of statistical effects in rounding Error propagation"
David S. Watkins - One of the best experts on this subject based on the ideXlab platform.
-
fast and Backward stable computation of roots of polynomials part ii Backward Error analysis companion matrix and companion pencil
SIAM Journal on Matrix Analysis and Applications, 2018Co-Authors: Jared L Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. WatkinsAbstract:This work is a continuation of work by [J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, J. Matrix Anal. Appl., 36 (2015), pp. 942--973]. In that paper we introduced a companion QR algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in $O(n^{2})$ time using $O(n)$ memory. We proved that the method is Backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved Backward Error analysis that takes advantage of the special structure of the problem. The improvement is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion QR algorithm, the Backward Error on the polynomial coefficients varies linearly with the norm of the polynomial's vector of coefficients. Thus, the companion QR algorithm has a sm...
-
fast and Backward stable computation of roots of polynomials part ii Backward Error analysis companion matrix and companion pencil
SIAM Journal on Matrix Analysis and Applications, 2018Co-Authors: Jared L Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. WatkinsAbstract:This work is a continuation of work by [J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, J. Matrix Anal. Appl., 36 (2015), pp. 942--973]. In that paper we introduced a companion QR algorith...
-
fast and Backward stable computation of roots of polynomials part ii Backward Error analysis companion matrix and companion pencil
arXiv: Numerical Analysis, 2016Co-Authors: Jared L Aurentz, Thomas Mach, Leonardo Robol, Raf Vandebril, David S. WatkinsAbstract:This work is a continuation of "Fast and Backward stable computation of roots of polynomials" by J.L. Aurentz, T. Mach, R. Vandebril, and D.S. Watkins, SIAM Journal on Matrix Analysis and Applications, 36(3): 942--973, 2015. In that paper we introduced a companion QR algorithm that finds the roots of a polynomial by computing the eigenvalues of the companion matrix in $O(n^{2})$ time using $O(n)$ memory. We proved that the method is Backward stable. Here we introduce, as an alternative, a companion QZ algorithm that solves a generalized eigenvalue problem for a companion pencil. More importantly, we provide an improved Backward Error analysis that takes advantage of the special structure of the problem. The improvement is also due, in part, to an improvement in the accuracy (in both theory and practice) of the turnover operation, which is the key component of our algorithms. We prove that for the companion QR algorithm, the Backward Error on the polynomial coefficients varies linearly with the norm of the polynomial's vector of coefficients. Thus the companion QR algorithm has a smaller Backward Error than the unstructured QR algorithm (used by MATLAB's \texttt{roots} command, for example), for which the Backward Error on the polynomial coefficients grows quadratically with the norm of the coefficient vector. The companion QZ algorithm has the same favorable Backward Error as companion QR, provided that the polynomial coefficients are properly scaled.
Gerhard Wanner - One of the best experts on this subject based on the ideXlab platform.
-
geometric numerical integration structure preserving algorithms for ordinary differential equations
2009Co-Authors: Ernst Hairer, Christian Lubich, Gerhard WannerAbstract:Examples and Numerical Experiments.- Numerical Integrators.- Order Conditions, Trees and B-Series.- Conservation of First Integrals and Methods on Manifolds.- Symmetric Integration and Reversibility.- Symplectic Integration of Hamiltonian Systems.- Non-Canonical Hamiltonian Systems.- Structure-Preserving Implementation.- Backward Error Analysis and Structure Preservation.- Hamiltonian Perturbation Theory and Symplectic Integrators.- Reversible Perturbation Theory and Symmetric Integrators.- Dissipatively Perturbed Hamiltonian and Reversible Systems.- Oscillatory Differential Equations with Constant High Frequencies.- Oscillatory Differential Equations with Varying High Frequencies.- Dynamics of Multistep Methods.
-
geometric numerical integration structure preserving algorithms for ordinary differential equations
2004Co-Authors: Ernst Hairer, Christian Lubich, Gerhard WannerAbstract:Numerical methods that preserve properties of Hamiltonian systems, reversible systems, differential equations on manifolds and problems with highly oscillatory solutions are the subject of this book. A complete self-contained theory of symplectic and symmetric methods, which include Runge-Kutta, composition, splitting, multistep and various specially designed integrators, is presented and their construction and practical merits are discussed. The long-time behaviour of the numerical solutions is studied using a Backward Error analysis (modified equations) combined with KAM theory. The book is illustrated by many figures, it treats applications from physics and astronomy and contains many numerical experiments and comparisons of different approaches. The second edition is substantially revised and enlarged, with many improvements in the presentation and additions concerning in particular non-canonical Hamiltonian systems, highly oscillatory mechanical systems, and the dynamics of multistep methods.
