|
Large part of important problems in pure and applied
mathematics involves structured matrices. The analysis of theoretical
and computational properties of these structures is a fundamental step
in the design of efficient algorithms specifically designed for these
problems especially in the very frequent cases where the general
solution algorithms cannot be applied due to the huge size of the
problem.
Matrix structures are inherited by the specific properties of the
problem. Common features shared by problems in different areas, like
shift invariance, compact support, separability of variables, turn into
structures which are common to matrices encountered in different
fields, like the Toeplitz structure, the displacement structure
(including Hankel, Cauchy, Bezout, Frobenius, Pick, Vandermonde
matrices), band matrices, semi-separable matrices, arrowhead matrices
etc. In fact, these structures are encountered in many different
problems in statistics, probability, queueing theory (including
telecommunications, internet, performance analysis, stochastic
processes), polynomial computations, computer algebra, Computer Aided
Geometric Design, numerical solution of differential and of integral
equations, image and signal processing just to quote a few.
Very often the properties of the original problem turn into structures
which are not so evident, say, nonlinear structures like displacement
structure, semi-separable or quasi-separable matrices, where the matrix
under analysis looks like a "general" matrix.
The analysis of matrix structures and the consequent design of specific
algorithms for solving problems in numerical linear algebra has
received a great attention and has produced important advances in the
algorithm design. On one hand, important theoretical advances have been
reached in the study of theoretical properties of certain structured
matrices, on the other hand the design of specific algorithms has
allowed the effective solution of important problems in different
applicative fields. Just to quote a few, algorithms for solving matrix
equations, or for solving queueing models based on Toeplitz
computations or on Wiener-Hopf factorization, recently designed,
allowed to reduce the cpu time of a large factor still maintaining very
good numerical performances [ALM]. In certain cases, the structured
matrix tools have provided fast solution of unstructured problems [D],
[DFLZ], [DLZ].
Summing up, the research of this unit are dictated by the following
general guidelines and motivations:
1- Structured matrices play a fundamental role in a great part of
mathematical models in applications and are almost pervasive.
2- The analysis of structured matrices, besides its theoretical
interest, is a fundamental step for the design of specific solution
algorithms. The results obtained in this way constitute a general
toolbox which is useful in many different contexts and situations and
constitutes the structured matrix technology.
3- The structured matrix technology can be used to effectively solve
large scale problems of great importance in the applications, which
could be hardly solved with general algorithms. At the same time, even
for the solution of general unstructured problems, the structured
matrix technology may provide important improvements.
4- The design and the analysis of algorithms taylored on the specific
structures of the problem is not enough in itself. It must be
integrated by a rigorous analysis of robustness and of numerical
stability. In certain situations where the ill conditioning is an
intrinsic feature of the problem, the use of multi-precision arithmetic
or the use of hybrid approaches based on symbolic and numeric tools
becomes a required step.
GENERAL RESARCH LINES
The research activity will be carried out according to the following
research lines:
-A- To perform the analysis of algebraic, structural, analytic,
spectral and computational properties of structured matrices which
intervene in theoretical and applied mathematics (including Toeplitz,
Hankel Bezout, Cauchy, Frobenius, and displacement generated matrices,
banded matrices, semi-separable and quasi-separable matrices, arrowhead
matrices, matrices with scalar entries and with blocks, multilevel
matrices).
-B- To exploit the properties obtained from this analysis for creating
general methodologies for the design and analysis of effective solution
algorithms.
-C- To apply the solution algorithms to problems coming from certain
applications and from large scale scientific computing.
-D- To implement, in terms of prototype software, the algorithms
designed in this research and to perform experimental validation and
comparison.
-E- To perform a theoretical or experimental rounding error analysis
and robustness analysis in order to select reliable algorithms. For
problems endowed of intrinsic ill conditioning, to design new
techniques based on the use of multiple precision arithmetic
complemented with the strategy of adaptiveness, and integrating
numerical and symbolic tools into hybrid algorithms.
SPECIFIC TOPICS:
Specific topics of our research are:
1- Polynomial computations: Analysis of (weak) Wiener-Hopf
factorizations where both the factors may have zeros of unit modulus.
Polynomial root-finders based on the QR algorithm applied to
generalized companion matrices which maintain the semi-separable (or
quasi-separable) structure. Polynomial rootfinders based on Newton's
and Laguerre's iteration whith Gerschgorin-like inclusion theorems and
the concepts of pseudozeros. Using the representation of polynomials in
the Bernstein basis together with their structured matrix counterpart
in order to design efficient algorithms for the intersection of Bezier
curves and of surfaces. Using hybrid techniques for the related
computational problems with tools in projective geometry, computer
algebra and numerical analysis. Computing eigenvalues of tridiagonal
matrices.
2- Matrix equations: the aim is designing algorithms for solving matrix
equations based on Wiener-Hopf factorizations. Algorithms for the
Riccati equation, algorithms for computing the principal p-th root of a
matrix.
3- Structural and computational properties of semi-separable,
quasi-separable matrices, Toeplitz matrices and matrices in
trigonometric algebras: one of the aim is designing algorithms for the
computation of eigenvalues and for polynomial rootfinders (see part 1)
4- Minimization problems: design and analysis of quasi-Newton
algorithms for minimization problems where the Hessian matrix is
approximated by a structured matrix. Solving total least squares
problems.
5- Applications of part 1) to solving Computer Aided Geometric Design
problems like intersection of curves and of surfaces parametrically or
implicitly assigned; application of part 2) to solving Markov chains
encountered in queueing models; application of part 3) to the design of
algorithms for polynomial rootfinding; application of part 4) to
solving neural networks.
MAIN TASKS
Concerning part 1) we wish to generalize and extend the shift
techniques introduced in [HMR], [BM7] for accelerating the convergence
of solving certain equations in Markov chains, in order to deal with
more general cases where the Wiener-Hopf factors may have zeros of
modulus 1.
-- We wish also to investigate more closely on the algorithm designed
in [BDG] where the QR iteration applied to an nxn Frobenius matrix is
performed in O(n) ops per step. Here the main issues concern numerical
stability and robustness. Also the algorithm introduced in [BGP] for
the computation of the eigenvalues of a subclass of quasi-separable
matrices will be closely investigated. Here the goal is to obtain an
efficient polynomial rootfinder and investigate on a possible
generalization of the class of matrices for which the QR iteration is
closed.
-- Polynomial rootfinders will be analyzed also in terms of
simultaneous and independent iterations based on the result of [HSS]
trying to replace Newton's iteration with the modified Laguerre
iteration and complementing it with some Gerschgorin like inclusion
theorems for the approximations provided by the algorithm.
-- Bernstein polynomials and Bezier curves will be investigated as
well. Here the main goal is to perform algebraic operations with
polynomials represented in the Bernstein basis without changing to the
power basis. In fact this transformation is severely ill conditioned.
This goal requires that the algebraic operations which are usally
performed in the power basis in terms of structured matrices (Bezout
and Sylvester matrices) be performed in the Bernstein basis.
Bernstein-Bezoutian metrices must be introduced and accurately
analyzed. Moreover algorithms for the LU or QR decomposition of such
matrices must be designed in such a way that either their numerical
implementation is numerically stable or their symbolic implementation
does not lead to a huge growth of the intermediate integers.
In this context, also the computation of the zeros of polynomials
represented in the Bernstein basis plays an important role and will be
investigated. Another related important topic is the application and
integration of numerical tools, symbolic tools, computer algebra and
projective geometry for solving computer aided geometric design
problems [Gianni].
Concerning part 2) we continue our study of [BM], [BGM1],[BGM2],[BG2]
on solving matrix equations. An important advance in this field was
introduced in [HMR], [BM7] in the context of Markov chains by means of
the "shift technique". Here we want to generalize this technique to
general matrix equations of polynomial type.
-- We want to apply the cyclic reduction algorithm of G. Golub [BGN]
adjusted to Markov chains by [BM3],[BM4] and analyzed in [BGM1],[BGM2]
to solving algebraic Riccati equations. Also the computation of the
principal p-th root of a matrix will be faced in terms of Wiener-Hopf
factorizations, Laurent series inversion and Newton's iteration.
-- Any kind of matrix equations modeling queueing problems will be
taken into account.
-- The problem of computing the p-th root of a matrix will be closely
investigated by using the techniques of [M4] and of [Ia].
Concerning part 3, we focus our attention on properties of
semi-separable and quasi-separable matrices with the aim of extending
the algorithms of [BDG] and [BGP] for implementing the QR iteration in
linear cost, to more general classes of matrices. This part is related
to some polynomial computations of part 1). Concerning Toeplitz
matrices and trigonometric algebras the interest is addressed to the
analysis of algebraic multigrid methods for solving the related systems.
Concerning part 4), we continue the study of [D], [DFLZ], [DLZ] with
the analysis of sufficient conditions which guarantee the convergence
of the quasi-Newton minimization techniques where the Hessian matrix is
replaced with a matrix in the Hartley algebra [BF] or with some
structured matrix. Here the conditions will concern the boundedness of
the operators appearing in the minimization process and on the
condition number of the structured matrix. Also adaptive methods where
the approximation of the Hessian is performed at each step of the
iteration will be studied. Algorithms for total least squares problems
for structured matrices will be analyzed with applications to blind
image deblurring.
Concerning part 5) of applications, we will apply our algorithms for
the listed applications. In particular, the results of 1) concerning
Bernstein-Bezout matrices, Bernstein polynomials and hybrid algorithms
will be applied to solving CAGD problems. We will apply the results of
2) to solving queueing models where the solution of the associated
matrix equations is the most expensive task, we will consider some
queueing models which are somehow related to the algebraic Riccati
equation. Concerning applications to Markov chains and to queueing
models, we planned to organize in Pisa in June 2005 the fifth edition
of the international conference "Matrix Analytic Methods in Stochastic
Models (MAM5)" which will be supported by this project. We will apply
the results of 4) to solving neural networks problems which model
automatic learning and to blind image restoration.
Part of the research in 3) on semi-separable and quasi-separable
matrices and on multigrid and on 4) on image deblurring is performed in
collaboration with the Unit of Genova.
[BG2] D.Bini,L.Gemignani, Solving quadratic matrix equations and
factoring polynomials: new fixed point iterations based on Schur
complements of Toeplitz matrices. To appear in Numer. Lin. Alg. Appl.
2004.
[BGFM] D.Bini, G.Fiorentino,,L.Gemignani,B.Meini, Effective fast
algorithms for polynomial spectral factorization , Numer. Algo., 2003.
[BGP] D.Bini,L.Gemignani,V.Pan $QR$-like algorithms for generalized
semiseparable matrices T.R. 1470, Dept. of Math., University of Pisa,
2003.
[BGT] D.Bini L.Gemignani F.Tisseur. The Ehrlich-Aberth method for the
nonsymmetric tridiagonal eigenvalue problem. TR 428, Univ. of
Manchester, England 2003
[BM7] D.Bini,B.Meini, Non-Skip-Free M/G/1-type Markov chains and
Laurent matrix power series, Proc. "Numerical Solution of Markov
Chains", Urbana, September 2003.
[FGPT] E.Fortuna, P.Gianni, P.Parenti, C.Traverso, Algorithms to
compute the topology of orientable real algebraic surfaces, J. Symb.
Comp., 36,2003
[HMR] C.He, B.Meini, N.Rhee, A shifted cyclic reduction algorithm for
QBDs, SIMAX,23 2001/02.
[HSS] J.Hubbard,D.Schleicher,S.Sutherland, How to find all roots of
complex polynomials by Newton's method. Invent. Math. 146 (2001).
[ALM] G.Anastasi, L.Lenzini, B.Meini, Performance evaluation of a worst
case model of the MetaRing MAC protocol with global fairness. Performance Evaluation, 29:127--151, 1997.
|