459 research outputs found
An ergodic theorem for classes of preconditioned matrices
No full textAbstractWe consider abstract classes of matrices {A} satisfying some structural conditions and, in particular, satisfying a crucial assumption about the asymptotic distribution of eigenvalues. We prove a similar distribution property for classes of preconditioned matrices constructed by using representants of {A}. As a particular case, this result applies to preconditioned matrices coming from several important contexts: Finite Differences and Faedo-Ritz-Galerkin linear systems associated with elliptic and semielliptic boundary value problems, very general Hermitian Toeplitz structures generated by multivariate Ll functions. This result answers in the positive some structural questions raised by Tyrtyshnikov [E. Tyrtyshnikov, Linear Algebra Appl. 207 (1994) 225–249] and by the author [S. Serra, Linear Algebra Appl. 267 (1997) 139–161; S. Serra, SIAM J. Numer. Anal., in press] in the Toeplitz context
Block generalized locally Toeplitz sequences: theory and applications in the multidimensional case. ETNA - Electronic Transactions on Numerical Analysis
No full textIn computational mathematics, when dealing with a large linear discrete problem (e.g., a linear system) arising from thenumerical discretization of a partial differential equation (PDE), knowledge of the spectral distribution of the associated matrix has proved to beuseful information for designing/analyzing appropriate solvers–-especially, preconditioned Krylov and multigrid solvers–-for the considered problem.Actually, this spectral information is of interest also in itself as long as the eigenvalues of the aforementioned matrix represent physical quantities of interest,which is the case for several problems from engineering and applied sciences (e.g., the study of natural vibration frequencies in an elastic material).The theory of multilevel generalized locally Toeplitz (GLT) sequences is a powerful apparatus for computing the asymptotic spectral distribution of matrices arising from virtually any kind of numerical discretization of PDEs. Indeed, when the mesh-fineness parameter tends to infinity, these matrices give rise to asequence , which often turns out to be a multilevel GLT sequence or one of its “relatives”, i.e., a multilevel block GLT sequence or a (multilevel) reduced GLTsequence. In particular, multilevel block GLT sequences are encountered in the discretization of systems of PDEs as well as in the higher-order finite element or discontinuousGalerkin approximation of scalar/vectorial PDEs.In this work, we systematically develop the theory of multilevel block GLT sequences as an extension of the theories of (unilevel) GLT sequences[Garoni and Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. I., Springer, Cham, 2017],multilevel GLT sequences[Garoni and Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. II., Springer, Cham, 2018],and block GLT sequences[Barbarino, Garoni, and Serra-Capizzano, Electron. Trans. Numer. Anal., 53 (2020), pp. 28–112].We also present several emblematic applications of this theory in the context of PDE discretizations
Two-level Toeplitz preconditioning: approximation results for matrices and functions
No full textLarge 2-level Toeplitz systems arise in a variety of applications (see, e.g., [R. H. Chan and M. Ng, SIAM Rev., 38 (1996), pp. 427-482]) for which efficient numerical methods for their solution are required. Some successful numerical techniques need the explicit knowledge of the generating function f of the considered system Tn(f)x = b, an assumption that usually is not fulfilled in real applications. In this paper we analyze and complete the procedure proposed in [D. Noutsas, S. Serra Capizzano, and P. Vassalos, Numer. Linear Algebra Appl., 12 (2005), pp. 231-239] for the 2-level case. In such a way, from the knowledge of the coefficients of Tn(f), we determine optimal preconditioning strategies for the solution of our systems. Finally, some numerical experiments are performed and discussed in connection with our theoretical analysis
Asymptotic zero distribution of orthogonal polynomials with discontinously varying recurrence coefficients
No full textThe zero distribution of orthogonal polynomials pn, N, n = 0, 1, ⋯ generated by recurrence coefficients an, N and bn, N depending on a parameter N has been recently considered by Kuijlaars and Van Assche under the assumption that an, N and bn, N behave like a(n/N) and b(n/N), respectively, where a(·) and b(·) are continuous functions. Here, we extend this result by allowing a(·) and b(·) to be measurable functions so that the presence of possible jumps is included. The novelty is also in the sense of the mathematical tools since, instead of applying complex analysis arguments, we use recently developed results from asymptotic matrix theory due to Tyrtyshnikov, Serra Capizzano, and Tilli
How to choose the best iterative strategy for symmetric Toeplitz systems
No full textIn the last decade many efficient iterative solvers for n × n symmetric (also Hermitian or generic) Toeplitz systems have been devised [R. H. Chan and G. Strang, SIAM J. Sci. Stat. Comput., 10 (1989), pp. 104-119; T. F. Chan, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 766-771; D. Bini and F. Di Benedetto, Proceedings, 2nd SPAA Conference, 1990, pp. 220-223; D. Bini and P. Favati, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 500-507; T. Huckle, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 767-777; F. Di Benedetto, G. Fiorentino, and S. Serra, Comput. Math. Appl., 26 (1993), pp. 35-45; S. Serra, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 1007-1019; G. Fiorentino and S. Serra, Calcolo, 28 (1991), pp. 283-305; S. Serra, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 31-44]. In all these methods it is assumed that the considered systems have the form An(f)x = b where the symbol f, the generating function, is an L1 function and the entries of An(f) along the kth diagonal coincide with the kth Fourier coefficient of f. The proof of convergence and sometimes even the definition of these solvers are derived by using some symbolic or analytic properties of f, while this function is often unknown in real applications. In this paper, by means of the knowledge of the coefficients of An(f) only, we propose and discuss an algorithm to economically determine the minimal features of f allowing us to choose and define the best iterative strategy. As a consequence of the analysis of the proposed procedure, we find some results on the structure of "quasi algebra" of the set {An(f)}f∈L1. Finally, we exhibit several numerical experiments which confirm the effectiveness of the proposed idea
Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions
No full textIt is well known that the generating function f ∈ L1([-π, π], R) of a class of Hermitian Toeplitz matrices {An(f)}n describes very precisely the spectrum of each matrix of the class. In this paper we consider n x n Hermitian block Toeplitz matrices with m x m blocks generated by a Hermitian matrix-valued generating function f ∈ L1([-π, π], Cm x m). We extend to this case some classical results by Grenander and Szegö holding when m = 1 and we generalize the Toeplitz preconditioning technique introduced in the scalar case by R. H. Chan and F. Di Benedetto, G. Fiorentino and S. Serra. Finally, concerning the spectra of the preconditioned matrices, some asymptotic distribution properties are demonstrated and, in particular, a Szegö-style theorem is proved. A few numerical experiments performed at the end of the paper confirm the correctness of the theoretical analysis
Sulle proprietà spettrali di matrici precondizionate di Toeplitz
No full textIn the present paper we survey some results recently proposed by the author about the spectral properties of preconditioned Toeplitz matrices and we discuss the deep connections with the elegant theory introduced by G Szegö for nonpreconditioned Toeplitz matrices. Then, we briefly stress the potentiality of this new mathematical tool both with respect to the design of fast resolution methods for Toeplitz (and Toeplitz-related) systems and with respect to the problem of evaluating the asymptotic condition numbers of such operator
Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear
No full textLet f be a d-variate 2π periodic continuous function and let {Tn(f)}n, n=(n1,⋯,nd), be the multiindexed sequence of multilevel N×N Toeplitz matrices (N=N(n)=∏ini) generated by f. Let A={A(N)}(N) be a sequence of matrix algebras simultaneously diagonalized by unitary transforms. We show that there exist infinitely many linearly independent trigonometric polynomials (and continuous nonpolynomial functions) f such that rankε(Tn(f)-PN)≠o(N(n)σi=1 dni -1) for any matrix sequence P={P(N)}∈A. This implies that no superlinear matrix algebra preconditioner exists in the multilevel Toeplitz case. The above mentioned result improves the analysis of the author and E. Tyrtyshnikov [SIAM J. Matrix Anal. Appl. 21 (2) (1999) 431] where the same was proved under the assumption that the involved algebras are of circulant type
The spectral approximation of multiplication operators via asymptotic (structured) linear algebra
No full textA multiplication operator on a Hilbert space may be approximated with finite sections by choosing an orthonormal basis of the Hilbert space. Multiplication operators with nonzero symbols, defined on L2 spaces of functions, are never compact and then such approximations cannot converge in the norm topology. Instead, we consider how well the spectra of the finite sections approximate the spectrum of the multiplication operator whose expression is simply given by the essential range of the symbol (i.e. the multiplier). We discuss the case of real orthogonal polynomial bases and the relations with the classical Fourier basis whose choice leads to the well studied Toeplitz case. Indeed, the asymptotic approximation of the spectrum by the spectra of the associated Toeplitz sections is possible only under precise geometric assumptions on the range of the symbol. Conversely, the use of circulant approximations leads to constructive algorithms, with O(N log(N)) complexity (N = number of sections), working in general and generalizable to the separable multivariate and matrix-valued cases as well
The GLT class as a generalized Fourier analysis and applications
No full textRecently, the class of Generalized Locally Toeplitz (GLT) sequences has been introduced as a generalization both of classical Toeplitz sequences and of variable coefficient differential operators and, for every sequence of the class, it has been demonstrated that it is possible to give a rigorous description of the asymptotic spectrum in terms of a function (the symbol) that can be easily identified. This generalizes the notion of a symbol for differential operators (discrete and continuous) or for Toeplitz sequences for which it is identified through the Fourier coefficients and is related to the classical Fourier Analysis. The GLT class has nice algebraic properties and indeed it has been proven that it is stable under linear combinations and products: in this paper we prove that the considered class is closed under inversion as well when the sequence which is inverted shows a sparsely vanishing symbol (sparsely vanishing symbol = a symbol which vanishes at most in a set of zero Lebesgue measure). Furthermore, we show that the GLT class virtually includes any Finite Difference or Finite Element discretization of PDEs and, based on this, we demonstrate that our results on GLT sequences can be used in a PDE setting in various directions: (1) as a generalized Fourier Analysis for the study of iterative and semi-iterative methods when dealing with variable coefficients, non-rectangular domains, non-uniform gridding or triangulations, (2) in order to provide a tool for the stability analysis of PDE numerical schemes (e.g., a necessary von Neumann criterium for variable coefficient systems of PDEs is obtained, uniformly with respect to the boundary conditions), (3) for a multigrid analysis of convergence and for providing spectral information on large preconditioned systems in the variable coefficient case, etc. The final part of the paper deals indeed with problems (1)-(3) and other possible directions in which the GLT analysis can be conveniently employed
- …
