Source author record

Vladimir Rokhlin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA Numerical Analysis math.CA math-ph math.MP

Catalog footprint

Research overview

10works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

A Provably Componentwise Backward Stable $O(n^2)$ QR Algorithm for the Diagonalization of Colleague Matrices

The roots of a monic polynomial expressed in a Chebyshev basis are known to be the eigenvalues of the so-called colleague matrix, which is a Hessenberg matrix that is the sum of a symmetric tridiagonal matrix and a rank-1 matrix. The rootfinding problem is thus reformulated as an eigenproblem, making the computation of the eigenvalues of such matrices a subject of significant practical importance. In this manuscript, we describe an $O(n^2)$ explicit structured QR algorithm for colleague matrices and prove that it is componentwise backward stable, in the sense that the backward error in the colleague matrix can be represented as relative perturbations to its components. A recent result of Noferini, Robol, and Vandebril shows that componentwise backward stability implies that the backward error $δc$ in the vector $c$ of Chebyshev expansion coefficients of the polynomial has the bound $\lVert δc \rVert \lesssim \lVert c \rVert u$ , where $u$ is machine precision. Thus, the algorithm we describe has both the optimal backward error in the coefficients and the optimal cost $O(n^2)$ . We illustrate the performance of the algorithm with several numerical examples.

preprint2020arXiv

A fast adaptive algorithm for scattering from a two dimensional radially-symmetric potential

In the present paper we describe a simple black box algorithm for efficiently and accurately solving scattering problems related to the scattering of time-harmonic waves from radially-symmetric potentials in two dimensions. The method uses FFTs to convert the problem into a set of decoupled second-kind Fredholm integral equations for the Fourier coefficients of the scattered field. Each of these integral equations are solved using scattering matrices, which exploit certain low-rank properties of the integral operators associated with the integral equations. The performance of the algorithm is illustrated with several numerical examples including scattering from singular and discontinuous potentials. Finally, the above approach can be easily extended to time-dependent problems. After outlining the necessary modifications we show numerical experiments illustrating the performance of the algorithm in this setting.

preprint2020arXiv

On the Numerical Solution of Fourth-Order Linear Two-Point Boundary Value Problems

This paper introduces a fast and numerically stable algorithm for the solution of fourth-order linear boundary value problems on an interval. This type of equation arises in a variety of settings in physics and signal processing. Our method reformulates the equation as a collection of second-kind integral equations defined on local subdomains. Each such equation can be stably discretized and solved. The boundary values of these local solutions are matched by solving a banded linear system. The method of deferred corrections is then used to increase the accuracy of the scheme. Deferred corrections requires applying the integral operator to a function on the entire domain, for which we provide an algorithm with linear cost. We illustrate the performance of our method on several numerical examples.

preprint2019arXiv

A fast simple algorithm for computing the potential of charges on a line

We present a fast method for evaluating expressions of the form $u_j = \sum_{i = 1,i \not = j}^n \frac{α_i}{x_i - x_j}, \quad \text{for} \quad j = 1,\ldots,n,$ where $α_i$ are real numbers, and $x_i$ are points in a compact interval of $\mathbb{R}$ . This expression can be viewed as representing the electrostatic potential generated by charges on a line in $\mathbb{R}^3$ . While fast algorithms for computing the electrostatic potential of general distributions of charges in $\mathbb{R}^3$ exist, in a number of situations in computational physics it is useful to have a simple and extremely fast method for evaluating the potential of charges on a line; we present such a method in this paper, and report numerical results for several examples.

preprint2015arXiv

Improved estimates for nonoscillatory phase functions

Recently, it was observed that solutions of a large class of highly oscillatory second order linear ordinary differential equations can be approximated using nonoscillatory phase functions. In particular, under mild assumptions on the coefficients and wavenumber $λ$ of the equation, there exists a function whose Fourier transform decays as $\exp(-μ|ξ|)$ and which represents solutions of the differential equation with accuracy on the order of $λ^{-1} \exp(-μλ)$ . In this article, we establish an improved existence theorem for nonoscillatory phase functions. Among other things, we show that solutions of second order linear ordinary differential equations can be represented with accuracy on the order of $λ^{-1} \exp(-μλ)$ using functions in the space of rapidly decaying Schwartz functions whose Fourier transforms are both exponentially decaying and compactly supported. These new observations play an important role in the analysis of a method for the numerical solution of second order ordinary differential equations whose running time is independent of the parameter $λ$ . This algorithm will be reported at a later date.

preprint2014arXiv

On the asymptotics of Bessel functions in the Fresnel regime

We introduce a version of the asymptotic expansions for Bessel functions $J_ν(z)$ , $Y_ν(z)$ that is valid whenever $|z| > ν$ (which is deep in the Fresnel regime), as opposed to the standard expansions that are applicable only in the Fraunhofer regime (i.e. when $|z| > ν^2$ ). As expected, in the Fraunhofer regime our asymptotics reduce to the classical ones. The approach is based on the observation that Bessel's equation admits a non-oscillatory phase function, and uses classical formulas to obtain an asymptotic expansion for this function; this in turn leads to both an analytical tool and a numerical scheme for the efficient evaluation of $J_ν(z)$ , $Y_ν(z)$ , as well as various related quantities. The effectiveness of the technique is demonstrated via several numerical examples. We also observe that the procedure admits far-reaching generalizations to wide classes of second order differential equations, to be reported at a later date.

preprint2014arXiv

On the existence of nonoscillatory phase functions for second order differential equations in the high-frequency regime

We observe that solutions of a large class of highly oscillatory second order linear ordinary differential equations can be approximated using nonoscillatory phase functions. In addition, we describe numerical experiments which illustrate important implications of this fact. For example, that many special functions of great interest --- such as the Bessel functions $J_ν$ and $Y_ν$ --- can be evaluated accurately using a number of operations which is $O(1)$ in the order $ν$ . The present paper is devoted to the development of an analytical apparatus. Numerical aspects of this work will be reported at a later date.

preprint2013arXiv

On the evaluation of prolate spheroidal wave functions and associated quadrature rules

As demonstrated by Slepian et. al. in a sequence of classical papers, prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. Recently, PSWFs have been becoming increasingly popular in various areas in which such functions occur - this includes physics (e.g. wave phenomena, fluid dynamics), engineering (signal processing, filter design), etc. To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of corresponding quadrature rules, interpolation formulas, etc. During the last 15 years, substantial progress has been made in the design of such algorithms. However, many of the existing algorithms tend to be relatively slow when $c$ is large (e.g. c>10^4). In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. While the analysis is somewhat involved and will be published separately, the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the $n$ th eigenvalue of the prolate integral operator requires $O(n+c \cdot \log c)$ operations; the construction of accurate quadrature rules for the integration (and associated interpolation) of bandlimited functions with band limit $c$ requires $O(c)$ operations. All algorithms described in this paper produce results essentially to machine precision. Our results are illustrated via several numerical experiments.

preprint2012arXiv

Detailed analysis of prolate quadratures and interpolation formulas

As demonstrated by Slepian et. al. in a sequence of classical papers, prolate spheroidal wave functions (PSWFs) provide a natural and efficient tool for computing with bandlimited functions defined on an interval. As a result, PSWFs are becoming increasing popular in various areas in which such function occur - this includes physics (e.g. wave phenomena, fluid dynamics), engineering (e.g. signal processing, filter design), etc. To use PSWFs as a computational tool, one needs fast and accurate numerical algorithms for the evaluation of PSWFs and related quantities, as well as for the construction of quadratures, interpolation formulas, etc. Even though, for the last half a century, substantial progress has been made in design of such algorithms, the complexity of many of the existing algorithms, however, is at least quadratic in the band limit $c$ . For example, the evaluation of the $n$ th eigenvalue of the prolate integral operator requires at least $O(c^2)$ operations. Therefore, while the existing algorithms are quite satisfactory for moderate values of $c$ (e.g. $c \leq 10^3$ ), they tend to be relatively slow when $c$ is large (e.g. $c \geq 10^4$ ). In this paper, we describe several numerical algorithms for the evaluation of PSWFs and related quantities, and design a class of PSWF-based quadratures for the integration of bandlimited functions. Also, we perform detailed analysis of the related properties of PSWFs. While the analysis is somewhat involved, the resulting numerical algorithms are quite simple and efficient in practice. For example, the evaluation of the $n$ th eigenvalue of the prolate integral operator requires $O(n+c)$ operations; also, the construction of related accurate quadrature rules requires $O(c)$ operations. Our results are illustrated via several numerical experiments.

preprint2009arXiv

A fast randomized algorithm for orthogonal projection

We describe an algorithm that, given any full-rank matrix A having fewer rows than columns, can rapidly compute the orthogonal projection of any vector onto the null space of A, as well as the orthogonal projection onto the row space of A, provided that both A and its adjoint can be applied rapidly to arbitrary vectors. As an intermediate step, the algorithm solves the overdetermined linear least-squares regression involving the adjoint of A (and so can be used for this, too). The basis of the algorithm is an obvious but numerically unstable scheme; suitable use of a preconditioner yields numerical stability. We generate the preconditioner rapidly via a randomized procedure that succeeds with extremely high probability. In many circumstances, the method can accelerate interior-point methods for convex optimization, such as linear programming (Ming Gu, personal communication).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Vladimir Rokhlin

Research overview

Is this your work?

10 publications

A Provably Componentwise Backward Stable $O(n^2)$ QR Algorithm for the Diagonalization of Colleague Matrices

A fast adaptive algorithm for scattering from a two dimensional radially-symmetric potential

On the Numerical Solution of Fourth-Order Linear Two-Point Boundary Value Problems

A fast simple algorithm for computing the potential of charges on a line

Improved estimates for nonoscillatory phase functions

On the asymptotics of Bessel functions in the Fresnel regime

On the existence of nonoscillatory phase functions for second order differential equations in the high-frequency regime

On the evaluation of prolate spheroidal wave functions and associated quadrature rules

Detailed analysis of prolate quadratures and interpolation formulas

A fast randomized algorithm for orthogonal projection

See the researcher in context

Building this map preview

Vladimir Rokhlin

Research overview

Is this your work?

10 publications

A Provably Componentwise Backward Stable O(n2)O(n^2)O(n2) QR Algorithm for the Diagonalization of Colleague Matrices

A fast adaptive algorithm for scattering from a two dimensional radially-symmetric potential

On the Numerical Solution of Fourth-Order Linear Two-Point Boundary Value Problems

A fast simple algorithm for computing the potential of charges on a line

Improved estimates for nonoscillatory phase functions

On the asymptotics of Bessel functions in the Fresnel regime

On the existence of nonoscillatory phase functions for second order differential equations in the high-frequency regime

On the evaluation of prolate spheroidal wave functions and associated quadrature rules

Detailed analysis of prolate quadratures and interpolation formulas

A fast randomized algorithm for orthogonal projection

See the researcher in context

Building this map preview

A Provably Componentwise Backward Stable $O(n^2)$ QR Algorithm for the Diagonalization of Colleague Matrices