497 research outputs found
Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result
No full textIn the last two decades a lot of matrix algehra optimal and superlinear preconditioners (those assuring a strong clustering at the unity) have been proposed for the solution of polynomially ill-conditioned Toeplitz linear systems. The corresponding generalizations to multilevel structures do not preserve optimality neither superlinearity. Regarding the notion of superlinearity, it has been recently shown that this is simply impossible. Here we propose some ideas and a proof technique for demonstrating that also the spectral equivalence and the essential spectral equivalence (up to a constant number of diverging eigenvalues) are impossible and therefore the search for optimal matrix algebra preconditioners in the multilevel setting cannot be successful
A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems
No full textLarge 2-level Toeplitz systems arise in many applications and thus an efficient strategy for their solution is often needed. The already known methods require the explicit knowledge of the generating function ƒ of the considered system Tnm(ƒ)x=b, an assumption that usually is not fulfilled in real applications. In this paper, we extend to the 2-level case a technique proposed in the literature in such a way that, from the knowledge of the coefficients of Tnm(ƒ), we determine optimal preconditioning strategies for the solution of our systems. More precisely, we propose and analyse an algorithm for the economical computation of minimal features of ƒ that allow us to select optimal preconditioners. Finally, we perform various numerical experiments which fully confirm the effectiveness of the proposed idea
Block band Toeplitz preconditioners derived from generating function approximations: Analysis and applications
No full textWe are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments
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
A Young-Eidson's type algorithm for complex p-cyclic SOR spectra
No full textIn a recent work of ours we have solved the problem of the minimization of the spectral radius of the iteration matrix of a p-cyclic successive overrelaxation (SOR) method for the solution of the linear system Ax = b, when the matrix A is block p-cyclic consistently ordered, for what is known as the "one-point" problem, for any p greater than or equal to 3. Particular cases of the "one-point" problem were solved by Young, Varga, Kjellberg, Kredell, Russell and others. In the present work we develop a theory using the results of our previous one and solve first the "two-point" problem special cases of which were solved by Wrigley, Eiermann, Niethammer, Ruttan, Noutsos and others. Secondly, we generalize and extend our theory to cover the "many-point" problem and develop a Young-Eidson's type algorithm for its solution. As possible application areas we mention among others the best block p-cyclic repartitioning for the SOR method and the solution of large scale systems arising in queueing network problems in Markov analysis. (C) 1999 Elsevier Science Inc. All rights reserved.Linear Algebra and Its Application
The conditioning of FD matrix sequences coming from semi-elliptic differential equations
No full textIn this paper we are concerned with the study of spectral properties of the sequence of matrices {An (a)} coming from the discretization, using centered finite differences of minimal order, of elliptic (or semielliptic) differential operators L (a, u) of the form (1)fenced((- frac(d, d x) fenced(a (x) frac(d, d x) u (x)) = f (x) on Ω = (0, 1),; Dirichlet B.C. on ∂ Ω,))where the nonnegative, bounded coefficient function a (x) of the differential operator may have some isolated zeros in over(Ω, -) = Ω ∪ ∂ Ω. More precisely, we state and prove the explicit form of the inverse of {An (a)} and some formulas concerning the relations between the orders of zeros of a (x) and the asymptotic behavior of the minimal eigenvalue (condition number) of the related matrices. As a conclusion, and in connection with our theoretical findings, first we extend the analysis to higher order (semi-elliptic) differential operators, and then we present various numerical experiments, showing that similar results must hold true in 2D as well
A Young-Eidson's type algorithm for complex p-cyclic SOR spectra
No full textAbstractIn a recent work of ours we have solved the problem of the minimization of the spectral radius of the iteration matrix of ap-cyclic successive overrelaxation (SOR) method for the solution of the linear systemAx = b, when the matrixA is blockp-cyclic consistently ordered, for what is known as the “one-point” problem, for anyp ⩾ 3. Particular cases of the “one-point” problem were solved by Young, Varga, Kjellberg, Kredell, Russell and others. In the present work we develop a theory using the results of our previous one and solve first the“two-point” problem special cases of which were solved by Wrigley, Eiermann, Niethammer, Ruttan, Noutsos and others. Secondly, we generalize and extend our theory to cover the“many-point” problem and develop a Young-Eidson's type algorithm for its solution. As possible application areas we mention among others the best blockp-cyclic repartitioning for the SOR method are the solution of large scale systems arising in queueing network problems in Markov analysis
On the convergence domains of the p-cyclic SOR
No full textAbstractFor the solution of the linear system Ax = b, where A is block p-cyclic, the block SOR iterative method is to be considered. Suppose that the block Jacobi iteration matrix B, associated with A, has eigenvalues whose pth powers are all real of the same sign. The problem of the determination of the precise convergence domains of the SOR method in case A is also consistently ordered was solved by Hadjidimos, Li and Varga by using the Schur-Cohn algorithm. The same convergence domains were later recovered by other approaches too; specifically, Wild and Niethammer and also Noutsos, independently, used hypocycloidal curves. In this manuscript it is assumed that A is not consistently ordered but AT is. By using the Schur-Cohn algorithm we successfully determine, not only: (i) the precise SOR convergence domains, but also (ii) intervals for ϱ(B), the spectral radius of B, that directly imply that the optimal value of the SOR relaxation factor ω is equal to 1. In this work new results are obtained, some well-known ones are recovered or confirmed and a number of theoretical examples are investigated further. It is worth noting that among the new results, we derived something not quite expected; specifically, in many cases there exist pairs (ϱ(B), ω) for which the SOR method associated with the matrix A we consider converges while the corresponding SOR for the p-cyclic consistently ordered matrix AT does not
On the Perron–Frobenius theory for complex matrices
No full textAbstractWe extend here the Perron–Frobenius theory of nonnegative matrices to certain complex matrices. Following the generalization of the Perron–Frobenius theory to matrices that have some negative entries, given by Noutsos [14], we introduce here two types of extensions of the Perron–Frobenius theory to complex matrices. We present and prove here some sufficient conditions and some necessary and sufficient conditions for a complex matrix to have a Perron–Frobenius eigenpair. We apply this theory by introducing Perron–Frobenius splittings, as well as complex Perron–Frobenius splittings, for the solution of complex linear systems Ax=b, by classical iterative methods. Perron–Frobenius splittings constitute an extension of the well-known regular splittings, weak regular splittings and nonnegative splittings. Convergence and comparison properties are also given and proved
Essential spectral equivalence via multiple step preconditioning and applications to ill conditioned Toeplitz matrices
No full textIn this note, we study the fast solution of Toeplitz linear systems with coefficient matrix Tn(f), where the generating function f is nonnegative and has a unique zero at zero of any real positive order θ. As preconditioner we choose a matrix τn(f) belonging to the so-called τ algebra, which is diagonalized by the sine transform associated to the discrete Laplacian. In previous works, the spectral equivalence of the matrix sequences τn(f)n and Tn(f)n was proven under the assumption that the order of the zero is equal to 2: in other words the preconditioned matrix sequence τn-1(f)Tn(f)n has eigenvalues, which are uniformly away from zero and from infinity. Here we prove a partial generalization of the above result when θ2, i.e., for every θ>2, there exist mθ and a positive interval [αθ,βθ] such that all the eigenvalues of τn-1(f)Tn(f)n belong to this interval, except at most mθ outliers larger than βθ: while the essential bound from above is proven, the bound from below is only observed numerically. Such a nice property, already known only when θ is an even positive integer greater than 2, is coupled with the fact that the preconditioned sequence has an eigenvalue cluster at one, so that the convergence rate of the associated preconditioned conjugate gradient method is optimal. As a conclusion we discuss possible generalizations and we present selected numerical experiments
- …
