| 1. |
- Bogoya, Manuel, et al.
(författare)
-
Fast Toeplitz eigenvalue computations, joining interpolation-extrapolation matrix-less algorithms and simple-loop theory
- 2022
-
Ingår i: Numerical Algorithms. - : Springer Nature. - 1017-1398 .- 1572-9265. ; :91, s. 1653-1676
-
Tidskriftsartikel (refereegranskat)abstract
- Under appropriate technical assumptions, the simple-loop theory allows to derive various types of asymptotic expansions for the eigenvalues of Toeplitz matrices generated by a function f. Independently and under the milder hypothesis that f is even and monotone over [0,π], matrix-less algorithms have been developed for the fast eigenvalue computation of large Toeplitz matrices, within a linear complexity in the matrix order: behind the high efficiency of such algorithms there are the expansions predicted by the simple-loop theory, combined with the extrapolation idea. Here we focus our attention on a change of variable, followed by the asymptotic expansion of the new variable, and we adapt the matrix-less algorithm to the considered new setting. Numerical experiments show a higher precision (till machine precision) and the same linear computation cost, when compared with the matrix-less procedures already presented in the relevant literature. Among the advantages, we concisely mention the following: (a) when the coefficients of the simple-loop function are analytically known, the algorithm computes them perfectly; (b) while the proposed algorithm is better or at worst comparable to the previous ones for computing the inner eigenvalues, it is vastly better for the computation of the extreme eigenvalues; a mild deterioration in the quality of the numerical experiments is observed when dense Toeplitz matrices are considered, having generating function of low smoothness and not satisfying the simple-loop assumptions.
|
|
| 2. |
- Bogoya, Manuel, et al.
(författare)
-
Fast Toeplitz eigenvalue computations, joining interpolation-extrapolation matrix-less algorithms and simple-loop theory : The preconditioned setting
- 2024
-
Ingår i: Applied Mathematics and Computation. - : Elsevier. - 0096-3003 .- 1873-5649. ; 466
-
Tidskriftsartikel (refereegranskat)abstract
- Under appropriate technical assumptions, the simple-loop theory allows to derive various types of asymptotic expansions for the eigenvalues of Toeplitz matrices generated by a function f. Unfortunately, such a theory is not available in the preconditioning setting, that is for matrices of the form with real-valued, g nonnnegative and not identically zero almost everywhere. Independently and under the milder hypothesis that is even and monotonic over , matrix-less algorithms have been developed for the fast eigenvalue computation of large preconditioned matrices of the type above, within a linear complexity in the matrix order: behind the high efficiency of such algorithms there are the expansions as in the case , combined with the extrapolation idea, and hence we conjecture that the simple-loop theory has to be extended in such a new setting, as the numerics strongly suggest.Here we focus our attention on a change of variable, followed by the asymptotic expansion of the new variable, and we consider new matrix-less algorithms ad hoc for the current case.Numerical experiments show a much higher accuracy till machine precision and the same linear computational cost, when compared with the matrix-less procedures already proposed in the literature.
|
|
| 3. |
- Bogoya, Manuel, et al.
(författare)
-
Fine spectral estimates with applications to the optimally fast solution of large FDE linear systems
- 2022
-
Ingår i: BIT Numerical Mathematics. - : Springer Nature. - 0006-3835 .- 1572-9125. ; 62:4, s. 1417-1431
-
Tidskriftsartikel (refereegranskat)abstract
- In the present article we consider a type of matrices stemming in the context of the numerical approximation of distributed order fractional differential equations (FDEs). From one side they could look standard, since they are real, symmetric and positive definite. On the other hand they cause specific difficulties which prevent the successful use of classical tools. In particular the associated matrix-sequence, with respect to the matrix-size, is ill-conditioned and it is such that a generating function does not exists, but we face the problem of dealing with a sequence of generating functions with an intricate expression. Nevertheless, we obtain a real interval where the smallest eigenvalue belongs to, showing also its asymptotic behavior. We observe that the new bounds improve those already present in the literature and give more accurate pieces of spectral information, which are in fact used in the design of fast numerical algorithms for the associated large linear systems, approximating the given distributed order FDEs. Very satisfactory numerical results are presented and critically discussed, while a section with conclusions and open problems ends the current work.
|
|
| 4. |
- Bogoya, Manuel, et al.
(författare)
-
Matrix-less methods for the spectral approximation of large non-Hermitian Toeplitz matrices : A concise theoretical analysis and a numerical study
- 2024
-
Ingår i: Numerical Linear Algebra with Applications. - : Wiley. - 1070-5325 .- 1099-1506.
-
Tidskriftsartikel (refereegranskat)abstract
- It is known that the generating function of a sequence of Toeplitz matrices may not describe the asymptotic distribution of the eigenvalues of the considered matrix sequence in the non-Hermitian setting. In a recent work, under the assumption that the eigenvalues are real, admitting an asymptotic expansion whose first term is the distribution function, fast algorithms computing all the spectra were proposed in different settings. In the current work, we extend this idea to non-Hermitian Toeplitz matrices with complex eigenvalues, in the case where the range of the generating function does not disconnect the complex field or the limiting set of the spectra, as the matrix-size tends to infinity, has one nonclosed analytic arc. For a generating function having a power singularity, we prove the existence of an asymptotic expansion, that can be used as a theoretical base for the respective numerical algorithm. Different generating functions are explored, highlighting different numerical and theoretical aspects; for example, non-Hermitian and complex symmetric matrix sequences, the reconstruction of the generating function, a consistent eigenvalue ordering, the requirements of high-precision data types. Several numerical experiments are reported and critically discussed, and avenues of possible future research are presented.
|
|
| 5. |
- Bogoya, Manuel, et al.
(författare)
-
On the extreme eigenvalues and asymptotic conditioning of a class of Toeplitz matrix-sequences arising from fractional problems
- 2022
-
Ingår i: Linear and multilinear algebra. - : Informa UK Limited. - 0308-1087 .- 1563-5139. ; , s. 1-12
-
Tidskriftsartikel (refereegranskat)abstract
- The analysis of the spectral features of a Toeplitz matrix-sequence {Tn(f)}n∈N, generated by the function f∈L1([−π,π]), real-valued almost everywhere (a.e.), has been provided in great detail in the last century, as well as the study of the conditioning, when f is nonnegative a.e. Here we consider a novel type of problem arising in the numerical approximation of distributed-order fractional differential equations (FDEs), where the matrices under consideration take the form Tn=c0Tn(f0)+c1hhTn(f1)+c2h2hTn(f2)+⋯+cn−1h(n−1)hTn(fn−1),c0,c1,…,cn−1 belong to the interval [c∗,c∗] with c∗⩾c∗>0 independent of n, h=1n, fj∼gj, and gj(θ)=|θ|2−jh for every j=0,…,n−1. For nonnegative functions or sequences, the notation s(x)∼t(x) means that there exist positive constants c, d, independent of the variable x in the definition domain such that cs(x)⩽t(x)⩽ds(x) for any x. Since the resulting generating function depends on n, the standard theory cannot be applied and the analysis has to be performed using new ideas. Few selected numerical experiments are presented, also in connection with matrices that come from distributed-order FDE problems, and the adherence with the theoretical analysis is discussed, together with open questions and future investigations.
|
|
| 6. |
- Bogoya, Manuel, et al.
(författare)
-
Upper Hessenberg and Toeplitz Bohemian matrix sequences: a note on their asymptotical eigenvalues and singular values
- 2022
-
Ingår i: Electronic Transactions on Numerical Analysis. - : Osterreichische Akademie der Wissenschaften, Verlag. - 1068-9613. ; 55, s. 76-91
-
Tidskriftsartikel (refereegranskat)abstract
- In previous works, Bohemian matrices have attracted the attention of several researchers for theirrich combinatorial structure, and they have been studied intensively from several points of view, including height,determinants, characteristic polynomials, normality, and stability. Here we consider a selected number of examples ofupper Hessenberg and Toeplitz Bohemian matrix sequences whose entries belong to the population P = {0, ±1},and we propose a connection with the spectral theory of Toeplitz matrix sequences and Generalized Locally Toeplitz(GLT) matrix sequences in order to give results on the localization and asymptotical distribution of their spectra andsingular values. Numerical experiments that support the mathematical study are reported. A conclusion section endsthe note in order to illustrate the applicability of the proposed tools to more general cases.
|
|
