Search

In this paper a new O(N log3 N) solver for N £ N Toeplitz-like sys- tems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [2, 16], it exploits the displacement properties. In order to avoid the well known numerical instability of the explicit inversion, the new algorithm relies on the triangular factorization and back-substitution formula for the system seen as a 2£2 block system with blocks of half size. The same idea has been used in [19] to improve the numerical stability of superfast meth- ods based on the generalized Schur algorithm for positive de¯nite Toeplitz matrices, but the algorithm we propose can be applied also to nonsym- metric Toeplitz-like systems. The stability of the algorithm is examined through numerical experiments.

We consider the two-dimensional discrete nonnegatively constrained deconvolution problem, whose goal is to reconstruct an object x¤ from its image b obtained through an optical system and a®ected by noise. When the large size of the problem prevents regularization by ¯l- tering, iterative methods enjoying semiconvergence property, coupled with suitable strategies for enforcing nonnegativity, are suggested. For these methods an accurate detection of the stopping index is essential. In this paper we analyze various stopping rules and test their e®ect on three di®erent iterative regularizing methods, by a large experimenta- tion.

A double-phase algorithm, based on the block recursive LU decomposition, has been recently proposed to solve block Hessenberg systems with sparsity properties. In the first phase the information related to the factorization of A and required to solve the system, is computed and stored. The solution of the system is then computed in the second phase. In the present paper the algorithm is modified: the two phases are merged into a one-phase version having the same computational cost and allowing a saving of storage. Moreover, the corresponding non-recursive version of the new algorithm is presented, which is especially suitable to solve infinite systems where the coefficient matrix dimension is not a priori fixed and a subsequent size enlargement technique is used. A special version of the algorithm, well suited to deal with block Hessenberg matrices having also a block band structure, is presented. Theoretical asymptotic bounds on the computational costs are proved. They indicate that, under suitable sparsity conditions, the proposed algorithms outperform Gaussian elimination. Numerical experiments have been carried out, showing the effectiveness of the algorithms when the size of the system is of practical interest.