401 citations · 707 across the 50 of their papers we have counts for
44 papers · 1 filter
AAA rational approximation on a continuum
Toby Driscoll, Yuji Nakatsukasa, Lloyd N. Trefethen
AAA rational approximation has normally been carried out on a discrete set, typically hundreds or thousands of points in a real interval or complex domain. Here we introduce a cont…
Are sketch-and-precondition least squares solvers numerically stable?
Maike Meier, Yuji Nakatsukasa, Alex Townsend +1
Sketch-and-precondition techniques are efficient and popular for solving large least squares (LS) problems of the form with and . This i…
Convergence and Near-optimal Sampling for Multivariate Function Approximations in Irregular Domains via Vandermonde with Arnoldi
Wenqi Zhu, Yuji Nakatsukasa
Vandermonde matrices are usually exponentially ill-conditioned and often result in unstable approximations. In this paper, we introduce and analyze the \textit{multivariate Vanderm…
Speeding up Krylov subspace methods for computing f(A)b via randomization
Alice Cortinovis, Daniel Kressner, Yuji Nakatsukasa
This work is concerned with the computation of the action of a matrix function f(A), such as the matrix exponential or the matrix square root, on a vector b. For a general matrix A…
Randomized low-rank approximation for symmetric indefinite matrices
Taejun Park, Yuji Nakatsukasa
The Nyström method is a popular choice for finding a low-rank approximation to a symmetric positive semi-definite matrix. The method can fail when applied to symmetric indefinite m…
Efficient Bounds and Estimates for Canonical Angles in Randomized Subspace Approximations
Yijun Dong, Per-Gunnar Martinsson, Yuji Nakatsukasa
Randomized subspace approximation with "matrix sketching" is an effective approach for constructing approximate partial singular value decompositions (SVDs) of large matrices. The…
A Fast Randomized Algorithm for Computing an Approximate Null Space
Yuji Nakatsukasa, Taejun Park
Randomized algorithms in numerical linear algebra can be fast, scalable and robust. This paper examines the effect of sketching on the right singular vectors corresponding to the s…
A Structure-Preserving Divide-and-Conquer Method for Pseudosymmetric Matrices
Peter Benner, Yuji Nakatsukasa, Carolin Penke
We devise a spectral divide-and-conquer scheme for matrices that are self-adjoint with respect to a given indefinite scalar product (i.e. pseudosymmetic matrices). The pseudosymmet…
Randomized algorithms for Tikhonov regularization in linear least squares
Maike Meier, Yuji Nakatsukasa
We describe two algorithms to efficiently solve regularized linear least squares systems based on sketching. The algorithms compute preconditioners for $\min \|Ax-b\|^2_2 + λ\|x\|^…
Rectangular eigenvalue problems
Behnam Hashemi, Yuji Nakatsukasa, Lloyd N. Trefethen
Often the easiest way to discretize an ordinary or partial differential equation is by a rectangular numerical method, in which n basis functions are sampled at m>>n collocation po…
Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems
Yuji Nakatsukasa, Joel A. Tropp
This paper develops a new class of algorithms for general linear systems and eigenvalue problems. These algorithms apply fast randomized sketching to accelerate subspace projection…
Least-squares spectral methods for ODE eigenvalue problems
Behnam Hashemi, Yuji Nakatsukasa
We develop spectral methods for ODEs and operator eigenvalue problems that are based on a least-squares formulation of the problem. The key tool is a method for rectangular general…
Full operator preconditioning and the accuracy of solving linear systems
Stephan Mohr, Yuji Nakatsukasa, Carolina Urzúa-Torres
Unless special conditions apply, the attempt to solve ill-conditioned systems of linear equations with standard numerical methods leads to uncontrollably high numerical error. Ofte…
Fast randomized numerical rank estimation for numerically low-rank matrices
Maike Meier, Yuji Nakatsukasa
Matrices with low-rank structure are ubiquitous in scientific computing. Choosing an appropriate rank is a key step in many computational algorithms that exploit low-rank structure…
High-Performance Partial Spectrum Computation for Symmetric eigenvalue problems and the SVD
D. Keyes, H. Ltaief, Y. Nakatsukasa +1
Current dense symmetric eigenvalue (EIG) and singular value decomposition (SVD) implementations may suffer from the lack of concurrency during the tridiagonal and bidiagonal reduct…
Stable and Efficient Computation of Generalized Polar Decompositions
Peter Benner, Yuji Nakatsukasa, Carolin Penke
We present methods for computing the generalized polar decomposition of a matrix based on the dynamically weighted Halley (DWH) iteration. This method is well established for compu…
Twice is enough for dangerous eigenvalues
Andrew Horning, Yuji Nakatsukasa
We analyze the stability of a class of eigensolvers that target interior eigenvalues with rational filters. We show that subspace iteration with a rational filter is robust even wh…
Reciprocal-log approximation and planar PDE solvers
Yuji Nakatsukasa, Lloyd N. Trefethen
This article is about both approximation theory and the numerical solution of partial differential equations (PDEs). First we introduce the notion of {\em reciprocal-log} or {\em l…
Fast and stable randomized low-rank matrix approximation
Yuji Nakatsukasa
Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson, and Tropp (…
Solving two-parameter eigenvalue problems using an alternating method
Henrik Eisenmann, Yuji Nakatsukasa
We present a new approach to compute selected eigenvalues and eigenvectors of the two-parameter eigenvalue problem. Our method requires computing generalized eigenvalue problems of…
Exponential node clustering at singularities for rational approximation, quadrature, and PDEs
Lloyd N. Trefethen, Yuji Nakatsukasa, J. A. C. Weideman
Rational approximations of functions with singularities can converge at a root-exponential rate if the poles are exponentially clustered. We begin by reviewing this effect in minim…
Vandermonde with Arnoldi
Pablo D. Brubeck, Yuji Nakatsukasa, Lloyd N. Trefethen
Vandermonde matrices are exponentially ill-conditioned, rendering the familiar "polyval(polyfit)" algorithm for polynomial interpolation and least-squares fitting ineffective at hi…
An algorithm for real and complex rational minimax approximation
Yuji Nakatsukasa, Lloyd N. Trefethen
Rational minimax approximation of real functions on real intervals is an established topic, but when it comes to complex functions or domains, there appear to be no algorithms curr…
Accuracy of approximate projection to the semidefinite cone
Paul J. Goulart, Yuji Nakatsukasa, Nikitas Rontsis
When a projection of a symmetric or Hermitian matrix to the positive semidefinite cone is computed approximately (or to working precision on a computer), a natural question is to q…