Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing Markov functions of Toeplitz matrices
130
0
0.0
(
0
)
Added by
Bernhard Beckermann
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We investigate the problem of approximating the matrix function $f(A)$ by $r(A)$, with $f$ a Markov function, $r$ a rational interpolant of $f$, and $A$ a symmetric Toeplitz matrix. In a first step, we obtain a new upper bound for the relative interpolation error $1-r/f$ on the spectral interval of $A$. By minimizing this upper bound over all interpolation points, we obtain a new, simple and sharp a priori bound for the relative interpolation error. We then consider three different approaches of representing and computing the rational interpolant $r$. Theoretical and numerical evidence is given that any of these methods for a scalar argument allows to achieve high precision, even in the presence of finite precision arithmetic. We finally investigate the problem of efficiently evaluating $r(A)$, where it turns out that the relative error for a matrix argument is only small if we use a partial fraction decomposition for $r$ following Antoulas and Mayo. An important role is played by a new stopping criterion which ensures to automatically find the degree of $r$ leading to a small error, even in presence of finite precision arithmetic.
rate research
Read More
We study means of geometric type of quasi-Toeplitz matrices, that are semi-infinite matrices $A=(a_{i,j})_{i,j=1,2,ldots}$ of the form $A=T(a)+E$, where $E$ represents a compact operator, and $T(a)$ is a semi-infinite Toeplitz matrix associated with the function $a$, with Fourier series $sum_{ell=-infty}^{infty} a_ell e^{mathfrak i ell t}$, in the sense that $(T(a))_{i,j}=a_{j-i}$. If $a$ is rv and essentially bounded, then these matrices represent bounded self-adjoint operators on $ell^2$. We consider the case where $a$ is a continuous function, where quasi-Toeplitz matrices coincide with a classical Toeplitz algebra, and the case where $a$ is in the Wiener algebra, that is, has absolutely convergent Fourier series. We prove that if $a_1,ldots,a_p$ are continuous and positive functions, or are in the Wiener algebra with some further conditions, then means of geometric type, such as the ALM, the NBMP and the Karcher mean of quasi-Toeplitz positive definite matrices associated with $a_1,ldots,a_p$, are quasi-Toeplitz matrices associated with the geometric mean $(a_1cdots a_p)^{1/p}$, which differ only by the compact correction. We show by numerical tests that these operator means can be practically approximated.
Circulant preconditioners for functions of matrices have been recently of interest. In particular, several authors proposed the use of the optimal circulant preconditioners as well as the superoptimal circulant preconditioners in this context and numerically illustrated that such preconditioners are effective for certain functions of Toeplitz matrices. Motivated by their results, we propose in this work the absolute value superoptimal circulant preconditioners and provide several theorems that analytically show the effectiveness of such circulant preconditioners for systems defined by functions of Toeplitz matrices. Namely, we show that the eigenvalues of the preconditioned matrices are clustered around $pm 1$ and rapid convergence of Krylov subspace methods can therefore be expected. Moreover, we show that our results can be extended to functions of block Toeplitz matrices with Toeplitz blocks provided that the optimal block circulant matrices with circulant blocks are used as preconditioners. Numerical examples are given to support our theoretical results.
We propose several circulant preconditioners for systems defined by some functions $g$ of Toeplitz matrices $A_n$. In this paper we are interested in solving $g(A_n)mathbf{x}=mathbf{b}$ by the preconditioned conjugate method or the preconditioned minimal residual method, namely in the cases when $g(z)$ are the functions $e^{z}$, $sin{z}$ and $cos{z}$. Numerical results are given to show the effectiveness of the proposed preconditioners.
Kolmogorov famously proved that multivariate continuous functions can be represented as a superposition of a small number of univariate continuous functions, $$ f(x_1,dots,x_n) = sum_{q=0}^{2n+1} chi^q left( sum_{p=1}^n psi^{pq}(x_p) right).$$ Fridman cite{fridman} posed the best smoothness bound for the functions $psi^{pq}$, that such functions can be constructed to be Lipschitz continuous with constant 1. Previous algorithms to describe these inner functions have only been Holder continuous, such as those proposed by Koppen and Braun and Griebel. This is problematic, as pointed out by Griebel, in that non-smooth functions have very high storage/evaluation complexity, and this makes Kolmogorovs representation (KR) impractical using the standard definition of the inner functions. To date, no one has presented a method to compute a Lipschitz continuous inner function. In this paper, we revisit Kolmogorovs theorem along with Fridmans result. We examine a simple Lipschitz function which appear to satisfy the necessary criteria for Kolmogorovs representation, but fails in the limit. We then present a full solution to the problem, including an algorithm that computes such a Lipschitz function.
Many standard conversion matrices between coefficients in classical orthogonal polynomial expansions can be decomposed using diagonally-scaled Hadamard products involving Toeplitz and Hankel matrices. This allows us to derive $smash{mathcal{O}(N(log N)^2)}$ algorithms, based on the fast Fourier transform, for converting coefficients of a degree $N$ polynomial in one polynomial basis to coefficients in another. Numerical results show that this approach is competitive with state-of-the-art techniques, requires no precomputational cost, can be implemented in a handful of lines of code, and is easily adapted to extended precision arithmetic.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
