Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast polynomial transforms based on Toeplitz and Hankel matrices
164
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Numerical integration of the stiffness matrix in higher order finite element (FE) methods is recognized as one of the heaviest computational tasks in a FE solver. The problem becomes even more relevant when computing the Gram matrix in the algorithm of the Discontinuous Petrov Galerkin (DPG) FE methodology. Making use of 3D tensor-product shape functions, and the concept of sum factorization, known from standard high order FE and spectral methods, here we take advantage of this idea for the entire exact sequence of FE spaces defined on the hexahedron. The key piece to the presented algorithms is the exact sequence for the one-dimensional element, and use of hierarchical shape functions. Consistent with existing results, the presented algorithms for the integration of $H^1$, $H(text{curl})$, $H(text{div})$, and $L^2$ inner products, have the $O(p^7)$ computational complexity. Additionally, a modified version of the algorithms is proposed when the element map can be simplified, resulting in the reduced $O(p^6)$ complexity. Use of Legendre polynomials for shape functions is critical in this implementation. Computational experiments performed with $H^1$, $H(text{div})$ and $H(text{curl})$ test shape functions show good correspondence with the expected rates.
We study the asymptotics in n for n-dimensional Toeplitz determinants whose symbols possess Fisher-Hartwig singularities on a smooth background. We prove the general non-degenerate asymptotic behavior as conjectured by Basor and Tracy. We also obtain asymptotics of Hankel determinants on a finite interval as well as determinants of Toeplitz+Hankel type. Our analysis is based on a study of the related system of orthogonal polynomials on the unit circle using the Riemann-Hilbert approach.
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.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
