401 citations · 707 across the 50 of their papers we have counts for
56 papers
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…
Eigenvalue avoidance of structured matrices depending smoothly on a real parameter
Yuji Nakatsukasa, Vanni Noferini
We explore the concept of eigenvalue avoidance, which is well understood for real symmetric and Hermitian matrices, for other classes of structured matrices. We adopt a differentia…
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\|^…
Stochastic diagonal estimation: probabilistic bounds and an improved algorithm
Robert A. Baston, Yuji Nakatsukasa
We study the problem of estimating the diagonal of an implicitly given matrix . For such a matrix we have access to an oracle that allows us to evaluate the matrix vector produc…
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…
A theory of quantum subspace diagonalization
Ethan N. Epperly, Lin Lin, Yuji Nakatsukasa
Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large\rev{-}scale eigenvalue problems using quantum computers. Unfortunately, these met…
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…
Zolotarev's fifth and sixth problems
Evan S. Gawlik, Yuji Nakatsukasa
In an influential 1877 paper, Zolotarev asked and answered four questions about polynomial and rational approximation. We ask and answer two questions: what are the best rational a…
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…