Unit 2 research program
Research
description
This
research unit has the following skills:
- analysis
of numerical methods for inverse
problems
- development
of parallel algorithms and
applications
- software
implementation of tools in Matlab
and Mathematica environments
- automatic
error analysis
The
contribution of the research unit to the
project is mainly the analysis of
methods for large-scale optimization
problems arising in the discretization of
Fredholm first kind integral equations. The
discretization of compact linear operators
gives raise to ill-conditioned matrices
because their minimum singular value is
closed to zero. The regularization methods
are introduced to filter out the components
relative to the small singular values
in the least squares solution. However, if
the singular values decrease with
exponential rate (i.e. in the so-called
"severely ill-posed" problems) we
cannot expect to compute any good solutions.
If there is a gap between the large and the
small singular values, then we can
expect to compute good solutions by means of
regularization methods, once the
regularization parameter has been suitably
chosen [H97].
The analysis of many regularization methods,
with respect to different techniques
for computing the regularization parameter,
must be performed by taking into account the
curve of the singular values [LPZ99].
Particular attention is given to the
definition of suitable stopping criteria to
regularize iterative methods based on on
Krylov iterations in general and on the
Conjugate Gradient iterations in particular
[LZ2000,LZ99,PZZF2001]. These methods
constitute the basic computational kernel of
the numerical packages for the solution of
many inverse problems in the area of image
restoration, tomographic
reconstruction, functional Magnetic
Resonance imaging, etc.
The behavior analysis of numerical
algorithms in finite precision arithmetic is
fundamental to the implementation of robust
software. Floating point systems, like those
based on IEEE standard [Ov], do not allow an
automatic tracing of rounding error
propagation. The formal analysis of errors
propagation is usually quite complex and it
is often left to Nume rical Analysis experts.
Recently, new attention has grown on
the possibility of embedding in software
tools for an automatic error control. In
[SS1,SS2,SS3] this possibility is studied
and developed within the Mathematica
computer algebra environment: the so called Significance
Arithmetic model is proposed and
implemented in the basic operations.
This research will focus on the following
objectives:
- combining
the power of parallel computing and
symbolic calculus, with the aim of
designing a software for the
analysis and automatic control
on the errors propagation. To this
end, where necessary, the ample
computing and memory resources of
parallel architectures will be
exploited together with the
arbitrarily high precision of the
symbolic environment. We propose to
study and develop Mathematica
software tools for the automatic
analysis of numerical stability
properties of the implemented
methods. The possibility of
employing Significance Arithmetic in
a flow of compound operations will
be investigated;
- realization
of efficient applications on
parallel architectures exploiting
the parallel nature of the different
problems. The domain decomposition
approach is used in the restoration
of images blurred with spatially
variant point spread functions. The
recent studies on the Hubble
telescope observations have inspired
new methods for the restoration of
blurred images. These methods are
based on the decomposition of
the spatially variant point spread
function into locally spatially
invariant patterns. The whole
image is then decomposed into square
patterns, each one restored by
means of a different spatially
invariant point spread function. An
overlap area is added to
preserve the continuity of the
reconstruction across the edges
[NO98].
The drawbacks of this approach
consist in the need to assume that a
spatially variant kernel can
be approximated by locally invariant
functions. This assumption is not
always applicable to real problems.
Our proposal is to exploit the
domain decomposition technique to
reduce the computational work for
classes of point spread
functions with smaller support with
respect to the image domain
[LPZ2001,BLP2000]. In this case we
have independent, small size,
ill-posed problems which can be
suitably solved by means of
iterative regularization methods
such as the Krylov iterations, or
the Tikhonov method coupled with
arrested Conjugate Gradients
iterations. A preconditioner for
such iterative methods can be
obtained by constructing
approximations of the point spread
function by means of gaussian
functions with variance constant on
each subdomain.
In the case of the reconstruction of
sequences of Dynamic Magnetic
Resonance images, we have to
solve a large size approximation
problem with undersampled data
in the Fourier domain. Such a
problem can be splitted in many
ill-conditioned, independent linear
systems, solved by means of a
regularization method [FLMZZ2000].
There is therefore a natural
parallelism in this problem that
makes it suitable for a solution
through a parallel approach.
References
|
[H97]
|
P.C.
Hansen, Rank Deficient and
Discrete Ill-Posed Problems:
Numerical Aspects of Linear
Inversion, SIAM (1997).
|
|
[NO98]
|
J.G.
Nagy, D.P. O'Leary, Restoring
Images Degraded by Spatially
Variant Blur, SIAM J.
on Sci. Comput. 19
(1998), 1063-1282.
|
|
[LPZ99]
|
E.
Loli Piccolomini, F. Zama, Regularization
Methods for the solution of
inverse problems: Theory and
computational aspects,
Rendiconti del Circolo
Matematico di Palermo, suppl.,
serie II 58 (1999),
173-183.
|
|
[LZ2000]
|
E.
Loli Piccolomini, F. Zama, Numerical
solution of some problems in
tomography, Ann. Univ.
Ferrara, sez. VII sc. mat., vol
XLV (2000), 115-127.
|
|
[FLMZZ2000
]
|
A.
Formiconi, E. Loli Piccolomini,
S. Martini, F. Zama, G.
Zanghirati, Numerical methods
and software for functional
magnetic resonance images
reconstruction, Ann.
Univ. Ferrara, sez. VII sc. mat.,
vol XLV (2000), 87-102.
|
|
[PZZF2001]
|
E.
Loli Piccolomini, F. Zama, G.
Zanghirati, A. Formiconi, Regularization
Methods in Dynamic MRI,
Applied Mathematics and
Computations 103 (2002).
|
|
[BLP2000]
|
E.
Loli Piccolomini, A. Bevilacqua,
Parallel image restoration on
paralleland distributed
computers, Parallel
Computing 26 (2000),
495-506.
|
|
[LPZ2001]
|
E.
Loli Piccolomini, F. Zama, Parallel
Image restoration with domain
decomposition, Real-Time
Imaging 7 (2001), 47-67.
|
|
[SS1]
|
M.
Sofroniou, G. Spaletta, Efficient
Computation of Continued
Fractions, Foundations of
Computational Mathematics (FoCM
99), July 1999, Oxford,
Inghilterra, 18-28.
|
|
[SS2]
|
M.
Sofroniou, G. Spaletta, Precise
Numerical Computation,
invited talk, Workshop
Arithmetique des Ordinateurs
Certifiee (Certified Arithmetic),
Ecole Normale Superieure,
November 15-16, 2000, Lione,
Francia.
|
|
[SS3]
|
M.
Sofroniou, G. Spaletta, Rounding
error reduction in extrapolation
methods, Workshop su
Numerical Methods for
Evolutionary Problems, September
17-21, 2001, Peschici, Foggia.
|
|
[Ov]
|
M.L.
Overton, Numerical Computing
with IEEE Floating Point
Arithmetic, SIAM editions,
Philadelphia, 2001.
|
[Top]
Research
Activities
Symbolic
calculus and parallel computing for error
propagation automatic control
Researchers.
G. Spaletta.
Description.
Combining the potential offered by parallel
computing with those of symbolic calculus,
we will design a software for the analysis
and automatic control on the error
propagation, by exploiting, where
necessary, the ample computing and memory
resources of parallel architectures
and at the same time the arbitrarily high
precision of the symbolic environment.
We propose to study and develop software
tools for the automatic analysis of
the numerical stability properties of
implemented methods in Mathematica. We will
study the possibility of employing
Significance Arithmetic in a flow of
compound operations.
Expected
results. Theoretical contributions to
the automatic error control. Design of
Computer Algebra tools devoted to the
automatic analysis of numerical
stability.
[Top]
Parallel
domain decomposition techniques for
space-variant blurred images restoration
Researchers.
F. Zama, E. Loli Piccolomini, G. Landi, M.
Bertaja.
Description.
Our proposal is to exploit the domain
decomposition technique in order to obtain
the restoration of an image pertubed by
space-variant gaussian point spread
function. In each subdomain we have to solve
a small size ill-posed problem; to
this end we will use iterative
regularization methods or Tikhonov method
coupled with arrested Conjugate Gradients
iterations. A preconditioner for such
iterative methods can be obtained by
constructing approximations of the the point
spread function by means of gaussian
functions with variance constant on each
subdomain. Parallel codes will be
developed and evaluated for the
effectiveness, on meaningful model
problems.
Expected
results. Analysis of the decomposition
approach for the image restoration problem.
Determination of some model problems;
development of a parallel
computational kernel based on the proposed
approach and its evaluation.
[Top]
A
parallel computing approach to dynamic
magnetic resonance imaging
Researchers.
F. Zama, E. Loli Piccolomini, G. Landi, M.
Bertaja.
Description.
In the case of the reconstruction of
sequences of dynamic magnetic
resonance images, we have to solve a large
size approximation problem with
undersampled data in the Fourier domain.
Such a problem can be splitted in many
ill-conditioned, independent linear systems,
solved by means of a regularization method.
There is therefore a natural parallelism in
this problem that makes it suitable for
parallel implementation. This approach
will be developed together with the related
parallel code. This code will be evaluated
on meaningful model problems arising from
the clinical routine.
Expected
results. Implementation of a parallel
code for the reconstruction of functional
magnetic resonance images and evaluation of
its effectiveness. Achievement of benchmark
also coming from the clinical routine, if
possible.
[Top]
|
|
