In a recent work Ng, Chan, and Tang introduced reflecting (Neumann) boundary conditions (BCs) for blurring models and proved that the resulting choice leads to fast algorithms for both deblurring and detecting the regularization parameters in the presence of noise. The key point is that Neumann BC matrices can be simultaneously diagonalized by the (fast) cosine transform DCT III. Here we propose antireflective BCs that can be related to $\tau$ structures, i.e., to the algebra of the matrices that can be simultaneously diagonalized by the (fast) sine transform DST I. We show that, in the generic case, this is a more natural modeling whose features are (a) a reduced analytical error since the zero (Dirichlet) BCs lead to discontinuity at the boundaries, the reflecting (Neumann) BCs lead to C⁰ continuity at the boundaries, while our proposal leads to C¹ continuity at the boundaries; (b) fast numerical algorithms in real arithmetic for both deblurring and estimating regularization parameters. Finally, simple yet significant 1D and 2D numerical evidence is presented and discussed.

Superlinear preconditioners (those that provide a proper cluster at 1) are very important for the cg-like methods since they make these methods converge superlinearly. As is well known, for Toeplitz matrices generated by a continuous symbol, many circulant and circulant-like (related to different matrix algebras) preconditioners were proved to be superlinear. In contrast, for multilevel Toeplitz matrices there has been no proof of the superlinearity of any multilevel circulants. In this paper we show that such a proof is not possible since any multilevel circulant preconditioner is not superlinear, in the general case of multilevel Toeplitz matrices. Moreover, for matrices not necessarily Toeplitz, we present some general results proving that many popular structured preconditioners cannot be superlinear.

In this paper we are interested in the solution by multigrid strategies of multilevel linear systems whose coefficient matrices belong to the circulant, Hartley, or $\tau$ algebras or to the Toeplitz class and are generated by (the Fourier expansion of) a nonnegative multivariate polynomial f. It is well known that these matrices are banded and have eigenvalues equally distributed as f, so they are ill-conditioned whenever f takes the zero value; they can even be singular and need a low-rank correction. We prove the V-cycle multigrid iteration to have a convergence rate independent of the dimension even in presence of ill-conditioning. If the (multilevel) coefficient matrix has partial dimension n_r at level r, r=1,...,d, then the size of the algebraic system is $N(n)=\prod_{r=1}^d n_r$, O(N(n)) operations are required by our technique, and therefore the corresponding method is optimal. Some numerical experiments concerning linear systems arising in applications, such as elliptic PDEs with mixed boundary conditions and image restoration problems, are considered and discussed.