Computing numerically with rational functions
MetadataShow full item record
Wilber, Heather Denise
New numerical methods using rational functions are presented for applications in linear algebra and signal processing. Classical results from Zolotarev are applied to develop a collection of low rank methods and theoretical results for computing with matrices that have special displacement structures using the alternating direction implicit (ADI) method. This includes a new low rank method for solving Sylvester and Lyapunov matrix equations with right hand sides that have decaying singular values, spectrally accurate low rank solvers for certain elliptic partial differential equations with smooth right-hand sides, and explicit bounds on the singular values of special families of structured matrices. Methods from conformal mapping and adaptive rational approximation are applied to build approximate solutions to Zolotarev's problem on sets where solutions are not known. This leads to new bounds on the numerical ranks of matrices, and it generalizes the regime in which ADI-based methods can be applied. The approximate solutions supply quasi-optimal ADI shift parameters for solving Sylvester matrix equations. A superfast rank-structured solver for Toeplitz linear systems is designed with ADI-based compression methods, and theoretical arguments are supplied that justify the effectiveness of rank-structured solvers for Toeplitz and related linear systems. The solvers are competitive with the state of the art, and rational approximation arguments are used to derive explicit error bounds on the numerical ranks of important submatrices for various weakly admissible hierarchical formats. A data-driven rational approximation framework is developed for reconstructing signals from samples with poorly separated spectral content. This approach combines a variant of Prony's method with a modified version of the AAA algorithm to construct representations of signals in both frequency and time space. The approximation methods are automatic and adaptive, requiring no tuning or manual parameter selection, and they are robust to various forms of corruption, including additive Gaussian noise, perturbed sampling grids, and missing data. A collection of algorithms and an accompanying software package for adaptively computing with these representations is introduced that includes procedures for differentiation/integration, rootfinding/polefinding, convolution, filtering, extrapolation, and more.
data-driven approximation; low rank approximation; matrix equations; numerical linear algebra; rational approximation; scientific computing
Townsend, Alex J.
Damle, Anil; Vladimirsky, Alexander B.
Ph. D., Applied Mathematics
Doctor of Philosophy
dissertation or thesis