1,721,001 research outputs found
Comparison of four natural bases for SPECT Imaging
No full textIn this paper the problem of restoring a two-dimensional tomographic medical image is considered. The emission function f(P) is defined on a planecircular domain Omega, and has to be restored from data collected by a SPECT machine. Through an approach known as natural pixel
discretization, the solution is expressed as a linear combination of functions
belonging to a suitable basis. We consider here four different bases, all of
them giving a highly structured coefficient matrix. The linear system obtained in this way can be solved efficiently by means of the fast Fourier transform.
The computational cost and the performance of the bases are compared. When the
data are contaminated by Poissonian noise, the numerical experimentation shows that all the bases are almost equivalent from the point of view of the restoration efficiency. Hence the choice of a basis should rely on other considerations, as for instance the computational cost
A Family of Modified Regularizing Circulant Preconditioners for Two-levels Toeplitz Systems
No full textComponentwise Conditioning of the DFT
No full textMixed and componentwise condition numbers are useful in order to understand stability properties of algorithms for solving
structured linear systems. The DFT (discrete Fourier transform) is an essential building block of these algoritms. We obtain estimates of mixed and componentwise condition numbers of the DFT. To this end, we explicitly compute certain special vectors that
share with their DFT the property of having entries with modulus equal to one
STABILITY OF THE LEVINSON ALGORITHM FOR TOEPLITZ-LIKE SYSTEMS
No full textNumerical stability of the Levinson algorithm, generalized for Toeplitz-like systems, is studied. Arguments based on the analytic results of an error analysis for floating point arithmetic produce an upper bound on the norm of the residual vector, which grows exponentially with respect to the size of the problem. The
base of such an exponential function can be small for diagonally dominant Toeplitz-like matrices.
Numerical experiments show that, for these matrices, Gaussian elimination by row and the Levinson algorithm have residuals of the same order of magnitude. As expected, the empirical results point out that the theoretical bound is too pessimistic
Recursive algorithms for unbalanced banded Toeplitz systems
No full textDirect recursive algorithms for the solution of band Toeplitz systems are here considered. They exploit the displacement rank properties, which allow a large reduction of computational efforts and storage requirements. Their use of the Sherman-Morrison-Woodbury formula turns out to be particularly suitable for the case of unbalanced bandwidths. The computational
costs of the algorithms under consideration are compared both in a theoretical and practical setting. Some stability issues are discussed as well
Railway computation for infinite linear systems
No full textThe problem of solving an infinite system of linear equations finitely expressed is addressed. Modifications of the Gauss-Seidel method are presented, especially suitable for the implementation on SMP machines with a small number of processors. One of the proposed parallel algorithms, which concentrates the computational efforts where they are most needed, results to be more efficient than the sequential algorithm, even from the point of view of the total number of operations
A stochastic model for the link analysis of the web
No full textAbstract. The behavior of inlink and outlink distributions appears to be one of the most studied properties of the web structure. The literature agrees that the inlink distribution follows a power law, but no such agreement exists for the outlink distribution. Accurate observations show that in the low-degree region the link distribution fails to fit a power law with a discrepancy larger for outlinks than for inlinks. Moreover, a power law, as well as any continuous function, does not fit the scattered behavior shared by both the link distributions for large-degree values. The linking model we consider here is a mixed one, based on both the preferential attachment strategy and the uniform attachment strategy. A new approximation technique is devised to detect the parameters of the steady state solution that describe a real data set. A stochastic technique is suggested to describe the scattering of the data. With these techniques the model appears to be well suited for describing both inlink and outlink distributions. The experimentation on subsets of the World Wide Web and of Wikipedia shows that our approach produces an approximation more adequate than the power law. This approximation suggests that the two attachment strategies play a different role in the inlink and the outlink cases
Preconditioners based on fit techniques for the iterative regularization in the image deconvolution problem
No full textFor large-scale image reconstruction problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n^2) operations per iteration, where n^2 is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is
of O(n^2 log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of
O(n^2) operations per iteration. A numerical experimentation shows that the fit preconditioners
Are competitive with the regularizing Chan preconditioner, both in the regularing efficiency and the computational cost
- …
