Nuova ricerca

Emanuele GALLIGANI

Professore Ordinario
Dipartimento di Ingegneria "Enzo Ferrari" sede ex-Matematica

Home | Curriculum(pdf) | Didattica |


Pubblicazioni

2022 - A generalization of the equivalence relations between modulus-based and projected splitting methods [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

2022 - Projected Splitting Methods for Vertical Linear Complementarity Problems [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

2021 - A generalization of irreducibility and diagonal dominance with applications to horizontal and vertical linear complementarity problems [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

2021 - Analysis of Resonant Soft X-ray Reflectivity of Anisotropic Layered Materials [Articolo su rivista]
Pasquali, Luca; Mahne, Nicola; Giglia, Angelo; Verna, Adriano; Sponza, Lorenzo; Capelli, Raffaella; Bonfatti, Matteo; Mezzadri, Francesco; Galligani, Emanuele; Nannarone, Stefano
abstract

We present here a method for the quantitative prediction of the spectroscopic specular reflectivity line-shape in anisotropic layered media. The method is based on a 4 × 4 matrix formalism and on the simulation from the first principles (through density functional theory—DFT) of the anisotropic absorption cross-section. The approach was used to simulate the reflectivity at the oxygen K-edge of a 3,4,9,10-perylene-tetracarboxylic dianhydride (PTCDA) thin film on Au(111). The effect of film thickness, orientation of the molecules, and grazing incidence angle were considered. The simulation results were compared to the experiment, permitting us to derive information on the film geometry, thickness, and morphology, as well as the electronic structure.

2021 - Modulus-based matrix splitting methods for a class of horizontal nonlinear complementarity problems [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

In this paper, we generalize modulus-based matrix splitting methods to a class of horizontal nonlinear complementarity problems (HNCPs). First, we write the HNCP as an implicit fixed-point equation and we introduce the proposed solution procedures. We then prove the convergence of the methods under some assumptions. We also comment on how the proposed methods and convergence theorems generalize existing results on (standard) linear and nonlinear complementarity problems and on horizontal linear complementarity problems. Finally, numerical experiments are solved to demonstrate the efficiency of the procedures. In this context, the effects of the splitting, of the dimension of the matrices, and of the nonlinear term of the problem are analyzed.

2020 - Modulus-based matrix splitting methods for horizontal linear complementarity problems [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

2020 - On the convergence of modulus-based matrix splitting methods for horizontal linear complementarity problems in hydrodynamic lubrication [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

2019 - A modulus-based nonsmooth Newton’s method for solving horizontal linear complementarity problems [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

2019 - A nonlinearity lagging method for non-steady diffusion equations with nonlinear convection terms [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

We analyze an iterative procedure for solving nonlinear algebraic systems arising from the discretization of nonlinear, non-steady reaction-convection-diffusion equations with non-constant (and, in general, nonlinear) velocity terms. The basic idea underlying the procedure consists in lagging the diffusion and the velocity terms of the discretized system, which is thus partly linearized. After analyzing the discretized system and proving some results on the monotonicity of the operators and on the uniqueness of the solution, we prove sufficient conditions that ensure the convergence of this lagged method. We also describe the inner iteration and show how the weakly nonlinear systems arising at each lagged iteration can be solved efficiently. Finally, we analyze numerically the entire solution process by several numerical experiments.

2019 - Performance analysis of Arithmetic Mean method for solving composite 6-point closed Newton-Cotes quadrature algebraic equation [Articolo su rivista]
Sundaram Muthuvalu, Mohana; Galligani, Emanuele; Khan Majahar Ali, Majid; Sulaiman, Jumat; Solomon Lebelo, Ramoshweu
abstract

The main focus of the paper is to study the performance of Arithmetic Mean (AM) iterative method in solving large and nonsingular dense linear system arising from the composite 6-point closed Newton–Cotes quadrature (6-CCNC) approximation of inhomogeneous linear Fredholm integral equations of the second kind. The derivation and implementation of the method are discussed. Some numerical results are also presented.

2019 - Splitting Methods for a Class of Horizontal Linear Complementarity Problems [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

In this paper, we propose two splitting methods for solving horizontal linear complementarity problems characterized by matrices with positive diagonal elements. The proposed procedures are based on the Jacobi and on the Gauss–Seidel iterations and differ from existing techniques in that they act directly and simultaneously on both matrices of the problem. We prove the convergence of the methods under some assumptions on the diagonal dominance of the matrices of the problem. Several numerical experiments, including large-scale problems of practical interest, demonstrate the capabilities of the proposed methods in various situations.

2018 - A lagged diffusivity method for reaction-convection-diffusion equations with Dirichlet boundary conditions [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

In this paper we solve a 2D nonlinear, non-steady reaction–convection–diffusion equation subject to Dirichlet boundary conditions by an iterative procedure consisting in lagging the diffusion term. First, we analyze the procedure, which we call Lagged Diffusivity Method. In particular, we provide a proof of the uniqueness of the solution and of the convergence of the lagged iteration when some assumptions are satisfied. We also describe outer and inner solvers, with special regard to how to link the stopping criteria in an efficient way. Numerical experiments are then introduced in order to evaluate the role of different linear solvers and of other components of the solution procedure, considering also the effect of the discretization.

2018 - An inexact Newton method for solving complementarity problems in hydrodynamic lubrication [Articolo su rivista]
Mezzadri, F.; Galligani, E.
abstract

We present an iterative procedure based on a damped inexact Newton iteration for solving linear complementarity problems. We introduce the method in the framework of a popular problem arising in mechanical engineering: the analysis of cavitation in lubricated contacts. In this context, we show how the perturbation and the damping parameter are chosen in our method and we prove the global convergence of the entire procedure. A Fortran implementation of the method is finally analyzed. First, we validate the procedure and analyze all its components, performing also a comparison with a recently proposed technique based on the Fischer–Burmeister–Newton iteration. Then, we solve a 2D problem and provide some insights on an efficient implementation of the method exploiting routines of the Lapack and of the PETSc packages for the solution of inner linear systems.

2017 - On the Lagged Diffusivity Method for the solution of nonlinear finite difference systems [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

In this paper, we extend the analysis of the Lagged Diffusivity Method for nonlinear, non-steady reaction-convection-diffusion equations. In particular, we describe how the method can be used to solve the systems arising from different discretization schemes, recalling some results on the convergence of the method itself. Moreover, we also analyze the behavior of the method in case of problems presenting boundary layers or blow-up solutions.

2016 - A Chebyshev technique for the solution of optimal control problems with nonlinear programming methods [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

This paper concerns with the solution of optimal control problems transcribed into nonlinear programming (NLP) problems by using approximations based on the Chebyshev series expansion. We first consider the relationship between the necessary conditions of the optimal control problem and the ones of the corresponding NLP problem. We then consider applying the Chebyshev based method to problems depending on both a time and a space variable by handling the space dependency with finite difference discretizations. We eventually write in AMPL language a collection of optimization problems (most of which includes also a space variable), which we solve with a series of solvers, so to analyze the behavior of the method and the influence on the solution of the parameters of the approximation and of the used solver.

2014 - A study of direct and Krylov iterative sparse solver techniques to approach linear scaling of the integration of chemical kinetics with detailed combustion mechanisms [Articolo su rivista]
Perini, Federico; Galligani, Emanuele; R. D., Reitz
abstract

The integration of the stiff ODE systems associated with chemical kinetics is the most computationally demanding task in most practical combustion simulations. The introduction of detailed reaction mechanisms in multi-dimensional simulations is limited by unfavorable scaling of the stiff ODE solution methods with the mechanism’s size. In this paper, we compare the efficiency and the appropriateness of direct and Krylov subspace sparse iterative solvers to speed-up the integration of combustion chemistry ODEs, with focus on their incorporation into multi-dimensional CFD codes through operator splitting. A suitable preconditioner formulation was addressed by using a general-purpose incomplete LU factorization method for the chemistry Jacobians, and optimizing its parameters using ignition delay simulations for practical fuels. All the calculations were run using a same efficient framework: SpeedCHEM, a recently developed library for gas-mixture kinetics that incorporates a sparse analytical approach for the ODE system functions. The solution was integrated through direct and Krylov subspace iteration implementations with different backward differentiation formula integrators for stiff ODE systems: LSODE, VODE, DASSL. Both ignition delay calculations, involving reaction mechanisms that ranged from 29 to 7171 species, and multi-dimensional internal combustion engine simulations with the KIVA code were used as test cases. All solvers showed similar robustness, and no integration failures were observed when using ILUT-preconditioned Krylov enabled integrators. We found that both solver approaches, coupled with efficient function evaluation numerics, were capable of scaling computational time requirements approximately linearly with the number of species. This allows up to three orders of magnitude speed-ups in comparison with the traditional dense solution approach. The direct solvers outperformed Krylov subspace solvers at mechanism sizes smaller than about 1000 species, while the Krylov approach allowed more than 40% speed-up over the direct solver when using the largest reaction mechanism with 7171 species.

2014 - Numerical studies on semi-implicit and implicit methods for reaction-diffusion equations [Working paper]
Galligani, Emanuele; Perini, Federico
abstract

In this report Rosenbrock, extended and generalized trapezoidal formulae are considered. Numerical studies on these methods have been developed on a linear and a nonlinear reaction diffusion convection equation.

2013 - A nonlinearity lagging for the solution of nonlinear steady state reaction diffusion problems [Articolo su rivista]
Galligani, Emanuele
abstract

This paper concerns with the analysis of the iterative procedure for the solution of a nonlinear reaction diffusion equation at the steady state in a two dimensional bounded domain supplemented by suitable boundary conditions. This procedure, called Lagged Diffusivity Functional Iteration (LDFI)-procedure, computes the solution by "lagging'' the diffusion term. A model problem is considered and a finite difference discretization for that model problem is described.Furthermore, properties of the finite difference operator are proved. Then, sufficient conditions for the convergence of the LDFI-procedure are given. At each stage of the LDFI-procedure a weakly nonlinearalgebraic system has to be solved and the simplified Newton-Arithmetic Mean method is used. This method is particularly well suited for implementation on parallel computers.Numerical studies show the efficiency, for different test functions, of the LDFI-procedure combined with the simplified Newton-Arithmetic Mean method. Better results are obtained when in the reaction diffusion equation also a convection term is present.

2013 - A note on the Rosenbrock formulae [Working paper]
Galligani, Emanuele; Perini, F.
abstract

In this report the Rosenbrock formulae are considered. These formulae are particularly suited for the integration of stiff differential systems such as the ones arising from reaction kinetics combustion modeling. The numerical techniques for the analysis of the A-stability and of the L-stability of a third order Rosenbrock formula are reported.

2013 - On the numerical solution of elliptic and parabolic optimal control problems [Articolo su rivista]
Mezzadri, Francesco; Galligani, Emanuele
abstract

This paper regards the solution of some optimal control problems, transcribed as constrained optimization problems, with the main purpose of analysing how the solution changes when the number of discretization points is modified. The problems studied, which include both boundary and distributed elliptic optimal control problems as well as parabolic control problems, have in fact been written in AMPL language and solved by changing the size of the discretization mesh, so to analyse the variance of the minimum of the objective as the number of discretization points increases. Moreover, the problems have been solved using different solvers (such as MINOS, LOQO, IPOPT, SNOPT and KNITRO) and different kinds of discretization so to consider the influence of these parameters on the final results.

2012 - An analytical Jacobian approach to sparse reaction kinetics for computationally efficient combustion modelling with large reaction mechanisms [Articolo su rivista]
Perini, Federico; Galligani, Emanuele; R. D., Reitz
abstract

This study presents an analytical Jacobian formulation for detailed gas-phase reaction kinetics, suitable for accurate and computationally efficient combustion simulations using either skeletal or detailed reaction mechanisms. A general chemical kinetics initial value problemin constant volume environments is considered, where the gas-phase mixture thermodynamic properties are polynomial functions of temperature according to the JANAF standard. Three different reaction behaviours are accounted for, including modified Arrhenius kinetic law reactions, third-body collisions, and pressure dependent reactions in Lindemann’s or Troe’s kinetic law forms. The integration of the chemistry ODE system is carried out using a software package specifically developed in Fortran language, and the solution compared to a reference chemical kinetics library. Two analytical Jacobian formulations, an exact one and a sparser, approximate one are proposed, and compared to numerical Jacobians computed by finite differences internally generated by a variety of commonly used stiff ordinary differential equations (ODE) solvers. The results show significant reductions in total computational times for the chemistry ranging from factors of 2 to more than two orders of magnitude for 29 species, 56 reactions to 2878 species, 8555 reactions, respectively. Finally, the code has been coupled to an engine combustion simulation software, where at each timestep the chemistry ODE system is integrated in each cell of the computational grid, allowing 77% faster computations with a 160 species combustion mechanism.

2012 - Analysis of the Fortran routines implementing the Arithmetic Mean method for the solution of block tridiagonal linear systems [Working paper]
Galligani, Emanuele
abstract

This report deals with the detailed analysis of the Fortran routines implementing the iterative method of the Arithmetic Mean for the solution of a linear algebraic system when the coefficient matrix has a block tridiagonal form.

2012 - Lagged diffusivity fixed point iteration for solving steady-state reaction diffusion problems [Articolo su rivista]
Galligani, Emanuele
abstract

The paper concerns with the computational algorithms for a steady-state reaction diffusion problem. A lagged diffusivity iterative algorithm is proposed for solving resulting system of quasilinear equations from a finite difference discretization. The convergence of the algorithm is discussed and the numerical results show the efficiency of this algorithm.

2012 - Lagged diffusivity method for the solution of nonlinear diffusion convection problems with finite differences [Articolo su rivista]
Galligani, Emanuele
abstract

This article concerns with the analysis of an iterative procedure for the solution of a nonlinear nonstationary diffusion convection equation in a two-dimensional bounded domain supplemented by Dirichlet boundary conditions. This procedure, denoted Lagged Diffusivity method, computes the solution by lagging the diffusion term. A model problem is considered and a finite difference discretization for thatmodel is described. Furthermore, properties of the finite difference operator are proved. Then, a sufficient condition for the convergence of the Lagged Diffusivity method is given. At each stage of the iterative procedure, a linear system has to be solved and the Arithmetic Mean method is used. Numerical experiments show theefficiency, for different test functions, of the Lagged Diffusivity method combined with the Arithmetic Mean method as inner solver. Better results are obtained when the convection term increases.

2012 - On solving optimal control problems for distributed parameter systems using an inexact Newton method [Capitolo/Saggio]
Galligani, Emanuele
abstract

This paper is concerned with the numerical solution of optimal control problems for distributed parameter systems by means of nonlinear programming methods. Specifically, we consider optimal control problems for systems described by reaction diffusion convection equations subject to control and state inequality constraints. We transcribe these problems into large finite dimensional nonlinear programming problems by introducing suitable finite difference discretization schemes. The numerical solutions of the above nonlinear programming problems are determined by solving the constrained system of nonlinear equations obtained by the Karush–Kuhn–Tucker (KKT) optimality conditions. For solving theseKKT system we use a Modified Inexact Newton (MIN) method. The convergence properties of the MIN method are stated under standard assumptions on the KKT systems. Numerical studies illustrate the outstanding features of the MIN method on problems of optimal control for distributed parameter systems described by time dependent and steady state diffusion equations.

2012 - The Arithmetic Mean solver in lagged diffusivity method for nonlinear diffusion equations [Articolo su rivista]
Galligani, Emanuele
abstract

This paper deals with the solution of nonlinear system arising from finite difference discretization of nonlinear diffusion convection equations by the lagged diffusivity functional iteration method combined with different inner iterative solvers. The analysis of the whole procedure with the splitting methods of the Arithmetic Mean(AM) and of the Alternating Group Explicit (AGE) has been developed. A comparison in terms of number of iterations has been done with the BiCG-STAB algorithm. Some numerical experiments have been carried out and they seem to show the effectiveness of the lagged diffusivity procedure with the Arithmetic Mean method as inner solver.

2012 - Validation of a Sparse Analytical Jacobian Chemistry Solver for Heavy-Duty Diesel Engine Simulations with Comprehensive Reaction Mechanisms [Relazione in Atti di Convegno]
Perini, Federico; Galligani, Emanuele; Cantore, Giuseppe; R., Reitz
abstract

The paper presents the development of a novel approach to the solution of detailed chemistry in internal combustion engine simulations, which relies on the analytical computation of the ordinary differential equations (ODE) system Jacobian matrix in sparse form. Arbitrary reaction behaviors in either Arrhenius, third-body or fall-off formulations can be considered, and thermodynamic gasphase mixture properties are evaluated according to the wellestablished 7-coefficient JANAF polynomial form. The current work presents a full validation of the new chemistry solver when coupled to the KIVA-4 code, through modeling of a single cylinder Caterpillar 3401 heavy-duty engine, running in two-stage combustion mode. The code has been tested on a wide range of simulations, at different injection timings, intake pressures, and EGR mass fractions, and considering two reaction mechanisms: a skeletal one with 29 species and 52 reactions, and a comprehensive, semi-detailed one with 160 species and 1540 reactions. The results show that the developed approach allows computational time savings of more than one order of magnitude in comparison to a reference chemistry solver, even with no reduction of the combustion mechanism size.

2011 - Application of inexact Newton method to the optimization of systems with distributed parameters [Working paper]
Galligani, Emanuele
abstract

This paper is concerned with the numerical solution of optimal control problems for distributed parameter systems by means of nonlinear programming methods. Specifically, we will consider optimal control problems for systems described by reaction diffusion convection equations subject to control and state inequality constraints. We assume that for these problems there exists a unique solution and the dynamic systems have an equilibrium state stable (in the sense of Lyapunov) and are completely controllable and observable. We transcribe these problems into large finite dimensional nonlinear programming problems by introducing suitable finite difference discretization schemes. A basic point of this transcription is a consistency condition for which the condition of optimality of the discretized problems (Karush–Kuhn–Tucker conditions) reflect the optimality conditions of the original continuous problems (Pontryagin Maximum Principle). This relationship between the discrete and the continuous necessary optimality conditions suggests to discretize the reaction diffusion convection equation with a finite difference scheme of type FTCS (Forward Time, Centered Space) which is second order accurate in space and first order accurate in time and is numerically stable in the sense of Von Neumann under suited conditions. The numerical solutions of the above nonlinear programming problems are determined by solving the constrained system of nonlinear equations obtained by the Karush–Kuhn–Tucker (KKT) optimality conditions. For solving these KKT system we use a Modified Inexact Newton (MIN) method. The convergence properties of the MIN method are stated under standard assumptions on the KKT systems. These assumptions are the same for which, at each iteration of the MIN method, the perturbed Newton equation has a unique solution, which can be determined by solving an equality constrained quadratic programming problem with the Hestenes’ method of multipliers. Numerical studies show that the MIN method leads to satisfactory results if we take care of choosing the starting point of the MIN iterative procedure and the perturbation parameter in such a way that the damping parameter is sufficiently large for all iterations.

2011 - Lagged diffusivity method for the solution of nonlinear diffusion convection problems with finite differences [Working paper]
Galligani, Emanuele
abstract

This paper concerns with the analysis of an iterative procedure for the solution of a nonlinear nonstationary diffusion convection equation in a two dimensional bounded domain supplemented by Dirichlet boundary conditions. This procedure, denoted Lagged Diffusivity method, computes the solution by lagging the diffusion term. A model problem is considered and a finite difference discretization for that model is described. Furthermore, properties of the finite difference operator are proved. Then, a sufficient condition for the convergence of the Lagged Diffusivity method is given. At each stage of the iterative procedure a linear system has to be solved and the Arithmetic Mean method is used. Numerical experiments show the efficiency, for different test functions, of the Lagged Diffusivity methodcombined with the Arithmetic Mean method as inner solver. Better results are obtained when the convection term increases.

2010 - A note on the iterative solution of nonlinear steady state reaction diffusion problems [Working paper]
Galligani, Emanuele
abstract

This report concerns with the numerical solution of nonlinear reaction diffusion equations at the steady state in a two dimensional bounded domain supplemented by suitable boundary conditions. When we use finite differences or finite element discretizations, the nonlinear diffusion equation subject to Dirichlet boundary conditions can be transcribed into a nonlinear system of algebraic equations. In the case of finite differences, the matrix that arises from the discretization of the diffusion (and/or convection) term satisfies properties of monotonicity.This report is divided into two parts (chapters): the first part deals with the solution of a weakly nonlinear reaction diffusion equation while in the second part, the solution of a strongly nonlinear reaction diffusion equation is computed by an iterative procedure that “lags” the diffusion term. This procedure is called Lagged Diffusivity Functional Iteration (LDFI)–procedure.In the first part the weakly nonlinear algebraic system arising from the discretization is solved by a simplified Newton method comkbined with the Arithmetic Mean method that is an iterative method, suited for parallel computers, for the solution of large sparse linear systems. This inner-outer iteration process gives a two-stage iterative method.Results concerning the global and monotone convergence for the two-stage iterative method have been reported. Furthermore, numerical experiments show the efficiency of the two-stage iterative method, especially for a dominant convection term, confirming the well known results for the linear case.In the second part the LDFI-procedure for the solution of the strongly nonlinear reaction diffusion equation is analyzed. A model problem is considered and a finite difference discretization for that model problem is described. Furthermore, in the report, properties of the finite difference operator are proved. Then, sufficient conditions for the convergence of the LDFI-procedure are given. At each stage of the LDFI-procedure a weakly nonlinear algebraic system has to be solved and the simplified Newton-Arithmetic Mean method is used. Numerical studies show the efficiency for different test functions of the LDFI-procedure combined with the simplified Newton-Arithmetic Mean method. Better result are obtained for dominant convection coefficients according with the linear and the weakly nonlinear cases.

2009 - On solving a special class of weakly nonlinear finite-difference systems [Articolo su rivista]
Galligani, Emanuele
abstract

In this paper, we consider the Newton-iterative method for solving weakly nonlinear finite-difference systems of the form F(u)=Au+G(u)=0, where the jacobian matrix G'(u) satisfies an affine invariant Lipschitz condition. We also consider a modification of the method for which we can improve the likelihood of convergence from initial approximations that may be outside the attraction ball of the Newton-iterative method. We analyse the convergence of this damped method in the framework of the line search strategy. Numerical experiments on a diffusion-convection problem show the effectiveness of the method.

2007 - A note on the iterative solution of weakly nonlinear elliptic control problems with control and state constraints [Working paper]
Galligani, Emanuele
abstract

This work concerns with the solution of optimal control problems by means of nonlinear programming methods. The control problem is transcribed into a finite dimensional nonlinear programming problem by finite difference approximation. An iterative procedure for the solution of this nonlinear program is presented. An extensive numerical analysis of the behaviour of the method is reported on boundary control and distributed control problems with boundary conditions of Dirichlet or Neumann or mixed type.

2007 - Inner solvers for interior point methods for large scale nonlinear programming [Articolo su rivista]
Bonettini, Silvia; Galligani, Emanuele; V., Ruggiero
abstract

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with an adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution.In this work, we analyse the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss the convergence of the whole approach, the implementation details and report the results of numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported.

2006 - The Arithmetic Mean method for solving systems of nonlinear equations in finite differences [Articolo su rivista]
Galligani, Emanuele
abstract

In this paper we consider the application of additive operator splitting methods for solving a finite difference nonlinear system of the form F(u) = (I - tau A(u))u - w = 0 generated by the discretization of two dimensional diffusion-convection problems with Neumann boundary conditions. Existence and uniqueness of a solution of this system has been proved under standard assumptions on the matrix A(u) and the source term w. Using the fact that the matrix A(u) can be decomposed into different splittings, we develop a nonlinear Arithmetic Mean method and a two-stage iterative method (a fixed-point-Arithmetic Mean method) for solving the system above. The convergence of these methods has been analyzed. Numerical experiments show that the fixed-point-Arithmetic Mean method is rapidly convergent when the diffusion coefficient is weakly nonlinear. (c) 2006 Elsevier Inc. All rights reserved.

2005 - Additive operator splitting methods for solving systems of nonlinear finite difference equations [Working paper]
Galligani, Emanuele
abstract

There exists a considerably body of literature on the development, analysis and implementation of multiplicative and additive operator splitting methods for solving large and sparse systems of finite difference equations arising from the discretization of partial differential equations. In this note, we will review the Newton-Arithmetic Mean and the Modified Newton-Arithmetic Mean methods for solving nonlinear and weakly nonlinear systems of difference equations arising from the discretization of diffusion-convection problems.

2005 - An inexact Newton method combined with Hestenes multipliers' scheme for the solution of Karush-Kuhn-Tucker systems [Articolo su rivista]
Bonettini, Silvia; Galligani, Emanuele; V., Ruggiero
abstract

In this work a Newton interior-point method for the solution of Karush-Kuhn-Tucker systems is presented.A crucial feature of this iterative method is the solution, at each iteration, of the inner subproblem. This subproblem is a linear-quadratic programming problem, that can solved approximately by an inner iterative method such as the Hestenes multipliers' method.A deep analysis on the choices of the parameters of the method (perturbation and damping parameters) has been done.The global convergence of the Newton interior-point method is proved when it is viewed as an inexact Newton method for the solution of nonlinear systems with restriction on the sign of some variables.The Newton interior-point method is numerically evaluated on large scale test problems arising from elliptic optimal control problems which show the effectiveness of the approach.

2005 - Inner solvers for interior point methods for large scale nonlinear programming [Working paper]
Bonettini, Silvia; Galligani, Emanuele; Ruggiero, V.
abstract

This paper deals with the solution of nonlinear programming problems arising from elliptic control problems by an interior point scheme. At each step of the scheme, we have to solve a large scale symmetric and indefinite system; inner iterative solvers, with adaptive stopping rule, can be used in order to avoid unnecessary inner iterations, especially when the current outer iterate is far from the solution. In this work, we analyze the method of multipliers and the preconditioned conjugate gradient method as inner solvers for interior point schemes. We discuss on the convergence of the whole approach, on the implementation details and we report results of a numerical experimentation on a set of large scale test problems arising from the discretization of elliptic control problems. A comparison with other interior point codes is also reported.

2005 - Iterative solution of elliptic control problems with control and state constraints [Articolo su rivista]
Galligani, Emanuele
abstract

This paper concerns with the solution of optimal control problems by means of nonlinear programming methods. The direct transcription,by finite difference approximation, of the optimal control problem into a finite dimensional nonlinear programming problem is described.An iterative procedure for the solution of this nonlinear program is presented. An extensive numerical analysis of the behaviour of the method isreported on boundary control and distributed control problems with boundary conditions of Dirichlet or Neumann or mixed type.

2005 - On solving a special class of weakly nonlinear finite difference systems [Working paper]
Galligani, Emanuele
abstract

In this paper we consider the Newton–iterative method for solving weakly nonlinear finite difference systems of the form F (u) = Au + G(u) = 0, where the Jacobian matrix G′(u) satisfies an affine invariant Lipschitz condition. We also consider a modification of the method for which we can improve the likelihood of convergence from initial approximations that may be outside the attraction ball of the Newton–iterative method. We analyse the convergence of this damped method in the framework of the line search strategy. Numerical experiments on a diffusion–convection problem show the effectiveness of the method.

2005 - Operator splitting methods for solving semidiscrete nonlinear diffusion problems [Working paper]
Galligani, Emanuele
abstract

Domain Decomposition and Operator Splitting are powerful concepts used in Parallel Computation and Large Scale Scientific Computation for the design of effective numerical methods.In this note, we will review various additive operator splitting methods for solving on parallel computers a large class of semidiscrete nonlinear diffusion problems.

2005 - Splitting methods for nonlinear diffusion filtering [Working paper]
Galligani, Emanuele; V., Ruggiero; G., Zanghirati
abstract

A PDE based method for image restoration is described by the heat equation with Neumann and initial conditions, where diffusivity is chosen as a rapidly decreasing function of the gradient magnitude of the solution and the initial condition represents the observed image. A widely used method for the numerical solution of this parabolic equation is the theta-method, that leads, at each time level, to a solution of a system of nonlinear equations of the form (I- tau A(u)) u= w, where the matrix A(u) satisfies irreducibility, vanishing column sum, negativity of diagonal entries and nonnegativity of the off-diagonal entries, Lipschitz continuity and symmetry. In this work we consider the application of splitting methods to the semi-implicit theta-method and to the implicit theta-method. In the case of semi-implicit theta-method, the Arithmetic Mean method is considered for the solution of the linear system that occurs at each time level; this method has within its overall mathematical structure certain well defined substructures that can be executed simultaneously in order to increase the degree of multiprogramming. For the solution of the nonlinear system that occurs at each time level of the implicit theta-method, multiplicative and additive operator splitting methods are examined. Because of the noncommutativity of the matrices of the splitting, the order of applying these matrices in the multiplicative operator splitting methods, as the AlternatingDirection Implicit or the Fractional Step methods, can affect the final result in image denoising. Indeed, the filtered two-dimensional image will not be the same after a rotation of 90 degrees. A symmetric strategy does not suffer from this deficiency; this motivates the advantage of using additive operator splitting methods in image restoration problems.

2004 - Analysis of the convergence of an inexact Newton method for solving Karush-Kuhn-Tucker systems [Articolo su rivista]
Galligani, Emanuele
abstract

In this paper we analyze an interior point method for solving perturbed Karush-Kuhn-Tucker systems in the framework of inexact Newton methods. This gives the possibility to revise the method to introduce an adaptive technique for changing the perturbation parameter and an inner linear solver for determining an approximate solution of the perturbed Newton equation. It makes the method more robust and highly effective for large-scale optimization problems, as those that occur in data fitting applications and in the discretization of optimal control problems governed by partial differential equations.

2004 - Hestenes method for symmetric indefinite systems in interior-point method [Articolo su rivista]
Bonettini, Silvia; Galligani, Emanuele; V., Ruggiero
abstract

This paper deals with the analysis and the solution of the Karush-Kuhn-Tucker (KKT) system that arises at each iteration of an Interior-Point (IP) method for minimizing a nonlinear function subject to equality and inequality constraints.This system is generally large and sparse and it can be reduced so that the coefficient matrix is still sparse, symmetric and indefinite, with size equal to the number of the primal variables and of the equality constraints. Instead of transforming this reduced system to a quasidefinite form by regularization techniques used in available codes on IP methods, under standard assumptions on the nonlinear problem, the system can be viewed as the optimality Lagrange conditions for a linear equality constrained quadratic programming problem, so that Hestenes multipliers' method can be applied. Numerical experiments on elliptic control problems with boundary and distributed control show the effectiveness of Hestenes scheme as inner solver for IP methods.

2003 - The Newton-arithmetic mean method for the solution of systems of nonlinear equations [Articolo su rivista]
Galligani, Emanuele
abstract

This paper is concerned with the development of the Newton-arithmetic mean method for large systems of nonlinear equations with block-partitioned Jacobian matrix. This method is well suited for implementation on a parallel computer; its degree of decomposition is very high. The convergence of the method is analysed for the class of systems whose Jacobian matrix satisfies an affine invariant Lipschitz condition. An estimation of the radius of the attraction ball is given. Special attention is reserved to the case of weakly nonlinear systems. A numerical example highlights some peculiar properties of the method. (C) 2002 Elsevier Science Inc. All rights reserved.

2003 - Variable projection methods for large-scale quadratic optimization in data analysis applications [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

This paper concerns with the numerical evaluation of the variable projection method for quadratic programming problems in three data analysis applications. The three applications give rise to large-scale quadratic programs with remarkable differences in the Hessian definition and/or in the structure of the constraints.

2002 - A perturbed-damped Newton method for large-scale constrained optimization [Working paper]
Galligani, Emanuele
abstract

In this work we analyze the Newton interior-point method presented in [El-Bakry, Tapia et al., J.Optim. Theory Appl., 89, 1996] for solving constrained systems of nonlinear equations arising from the Karush-Kuhn-Tucker conditions for nonlinear programming problems (KKT systems). More specifically, we consider a variant of the Newton interior-point method for KKT systems in in which the possibility to adaptively modify the perturbation parameter and the accuracy of the solution of the perturbed Newton equation, when one is still far away from the solution at an early stage, will moderate the difficulty of solving the KKT system. Using the results in [Durazzi, J.Optim. Theory Appl., 104, 2000] and [Bellavia, J.Optim. Theory Appl., 96, 1998], it is possible to establish a global convergence theory for this modified method. The method proposed in this work can be used effectively for large-scale optimization problems with structured sparsity, which occur, for instance, from the discretization of optimal control problems with inequality constraints.

2002 - A two-stage iterative method for solving a weakly nonlinear parametrized system [Articolo su rivista]
Galligani, Emanuele
abstract

In this paper we consider a parametrized system of weakly nonlinear equations which corresponds to a nonlinear elliptic boundary-value problem with zero source, homogeneous boundary conditions and a positive parameter in the linear term. Positive solutions of this system are of interest to us. A characterization of this positive solution is given. Such a solution is determined by the Modified Newton-Arithmetic Mean method. This method is well suited for implementation on parallel computers. A theorem about the monotone convergence of the method is proved. An application of the method for solving a real practical problem related to the study of interacting populations is described.

2002 - A two-stage iterative method for solving weakly nonlinear systems [Articolo su rivista]
Galligani, Emanuele
abstract

In this paper we consider a two-stage iterative method for solving weakly nonlinear systems generated by the discretization of semilinear elliptic boundary value problems. This method is well suited for implementation on parallel computers. Theorems about the convergence and the monotone convergence of the method are proved. An application of the method for solving real practical problems related to the study of reaction-diffusion processes and of interacting populations is described.

2002 - On a quadratic functional occurring in a bivariate scattered data interpolation problem [Articolo su rivista]
Galligani, Emanuele
abstract

The application of widely known blending methods for constructing C1 bivariate functions interpolating scattered data requires the knowledge of the partial derivatives of first order at the vertices of an underlying triangulation. In this paper we consider the method proposed by Nielson that consists in computing estimates of the first order partial derivatives by minimizing an appropriate quadratic functional, characterized by nonnegative tension parameters.The aim of the paper is to analyse some peculiar properties of this functional in order to construct robust and efficient algorithms for determining the above estimates of the derivatives when we are concerned with extremely large data sets.

2001 - Nonlinear programming methods for solving optimal control problems [Relazione in Atti di Convegno]
C., Durazzi; Galligani, Emanuele
abstract

This paper concerns with the problem of solving optimal control problems by means of nonlinear programming methods. The technique employed to obtain a mathematical programming problem from an optimal control problem is explained and the Newton interior-point method, chosen for its solution, is presented with special regard to the choice of the involved parameters. An analysis of the behaviour of the method is reported on four optimal control problems, related to improving water quality in an aeration process and to the study of diffusion convection processes.

2000 - On the stability of the direct elimination method for equality constrained least squares problems [Articolo su rivista]
Galligani, Emanuele; Zanni, Luca
abstract

A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example.

2000 - Projection-type methods for large convex quadratic programs: theory and computational experience [Working paper]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

A well-known approach to the solution of large and sparse linearly constrained quadratic programming (QP) problems is given by the classical projection and splitting methods. These methods have a similar iterative scheme consisting in to solve a sequence of QP subproblems with the constraints of the original problem and an easily solvable Hessian matrix. A theorem of convergence, resuming the main results about the projection and splitting methods, is given for this general scheme. In order to achieve a higher numerical performance than that obtained by projection and splitting methods, we introduce two variants of an iterative scheme that use a variable projection parameter at each step. These two variable projection-type methods differ in the strategy used to assure a sufficient decrease in the objective function f(x). We prove, under very general hypotheses, the convergence of these scheme and we propose two practical, nonexpensive and efficient updating rules for updating the projection parameter.An extensive numerical experimentation shows that the variable projection-type methods have an efficient behaviour.These results are produced by a set of programs available at the URL: http://www.unife.it/AnNum97/index.html. About the solution of the inner subproblems of the projection-type methods, we observe that, when the structure of the constraints does not suggest a particular solver for the QP inner subproblems, we can formulate each inner subproblem as a mixed linear complementarity problem (LCP) that can be solved by the classical projected SOR method of Cryer. When the number of constraints (and, consequently, the size of the inner LCPs) is large, appropriate parallel splitting methods for LCPs can be used for the solution on multiprocessor systems. Finally we describe two applications, arising in the framework of data analysis, that involve QP problems suited to be solved by projection-type methods.

2000 - Solution of discrete optimal control problems via mathematical programming [Relazione in Atti di Convegno]
C., Durazzi; Galligani, Emanuele
abstract

In this paper we consider the solution of discrete optimal control problems via mathematicalprogramming. In particular we examine iterative schemes, such as Hestenes' method of multipliers and interior-point method, which are suitable for linear-quadratic optimal control problems and for nonlinear optimal control problems respectively. Convergence results are reported as well as numerical evaluation of the effectiveness of these methods.

2000 - Surface fitting for extremely large scattered data sets [Working paper]
Galligani, Emanuele; M. A., Magnani
abstract

Given N pairwise distinct and arbitrarily spaced points V_i in a domain of the x-y plane and N real numbers z_i, consider the problem of computing a C1 bivariate function F(x,y) whose values in V_i are exactly z_i. In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires to minimize a quadratic functional; we prove that the hessian matrix is positive definite and is leading a P-regular splitting.

1999 - Numerical solution of discrete quadratic optimal control problems [Relazione in Atti di Convegno]
C., Durazzi; Galligani, Emanuele
abstract

This paper is concerned with the development of the Hestenes' method of multipliers combined with the conjugate gradient algorithm for solving discrete quadratic optimal control problems. This method is well suitable for parallel implementation on vector-parallel computers. Conditions for the convergence of the method are established and results of computational experiments, which are aimed at evaluating the effectiveness of the method, are reported.

1999 - Parallel solution of large Sylvester equations [Relazione in Atti di Convegno]
Galligani, Emanuele
abstract

Many problems in applied mathematics can be formulated as a Sylvester matrix equation AX+XB=C. Iterative methods for solving this equation are appropriate in applications coming from numerical treatment of elliptic problems and from control and systems theory. We determine the solution of this matrix equation with the Arithmetic Mean method, which is ideally suited for implementation on parallel computers. We consider different cases: A is large and sparse with a non random sparsity pattern and B is large with a simple structure; A and B are banded; A and B are large and without any special structure. The main purpose of this paper is to develop a convergence analysis of the method, using different splittings of the matrices A and B.

1999 - The proceedings of the workshop "Numerical Methods in Optimization" [Curatela]
A., Maugeri; Galligani, Emanuele
abstract

This special issue of Rendiconti del Circolo Matematico di Palermo consists of the lectures presented at the international workshop “Numerical Methods in Oprimization” held at Cortona during June 9-12, 1997.The workshop was organized by INdAM (Istituto Nazionale di Alta Matematica “Francesco Severi”) and partially supported by GNIM (Gruppo Nazionale per l’Informatica Matematica – CNR), CPS (Research Center on Parallel Computing and Supercomputers) and by EEC (HCMR Grant n. ERBCHECCT940253).The purpose of the workshop was to bring together mathematicians working in areas of Optimization where numerical methods play a basic role, so that they could not only present formal lectures, but also exchange ideas informally.The papers in this issue are arranged in alphabetic order of their authors’ name.Some papers deal with the solution to particular problems while others are devoted primarily to theoretical and numerical aspects of optimization. However, these latter papers also contain some problems of practical interest.This special issue of the journal Rendiconti del Circolo Matematico di Palermo allows a scientific continuity with the issue Serie II, Suppl. Volume 48, 1997 (edited by F. Giannessi, A. Maugeri and M. De Luca) containing the proceedings of the international worksop “Equilibrium Problems with Side Constraints, Lagrangean Theory and Duality II” held in Scilla, May 17-18, 1996.

1998 - A minimization method for the solution of large symmetric eigenproblems [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

This paper concerns with the solution of a special eigenvalue problem for a large sparse symmetric matrix by a fast convergent minimization method. A theoretical analysis of the method is developed; it is proved that is convergent with a convergence rate of fourth order. This minimization method requires to solve a sequence of equality-constrained least squares problems that become increasingly ill-conditioned, as the solution of eigenvalue problem is approached, A particular attention has been addressed to this question of ill-conditioning for the practical application of the method. Computational experiments carried out on Cray C90 show the behaviour of this minimization method as accelerating technique of the inverse iteration method. Also a comparison with the scaled Newton method has been done.

1998 - Parallel solution of large scale quadratic programs [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

We consider the solution of large and sparse linearly constrained quadratic programming problems. We describe an iterative scheme that requires to solve at each iteration a linear complementarity problem. For the solution of this last problem we examine parallel iterative solvers based on splittings of the complementarity matrix. We report the numerical results obtained by solving with the proposed approach quadratic programs on Cray T3E.

1998 - Parallel splitting methods for linearly constrained quadratic programs [Capitolo/Saggio]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

We consider the solution of large and sparse linearly constrained quadratic programming problems by an iterative scheme that requires to solve at each iteration a linear complementarity problem. For the solution of this last problem we examine parallel iterative solvers based on splittings of the complementarity matrix. We report the results of numerical experiments carried out on Cray T3E.

1997 - Error analysis in equality constrained quadratic optimization problems [Articolo su rivista]
Galligani, Emanuele; Zanni, Luca
abstract

In questo lavoro si considera la risoluzione numerica di problemi di programmazione quadratica con vincoli lineari di uguaglianza. Quando le dimensioni e la sparsità del problema sono particolarmente elevate, un approccio efficiente consiste nel trasformare il problema originario in una successione di sottoproblemi dello stesso tipo, ma di più facile risoluzione, mediante la decomposizione della matrice della funzione obiettivo. Il comportamento del metodo iterativo derivante da quest’approccio viene esaminato in corrispondenza alla scelta di due diverse strategie per la risoluzione dei sottoproblemi. Quando la matrice della funzione obiettivo e la matrice dei vincoli sono dense e di piccole o medie dimensioni, il problema originario può essere risolto con metodi diretti di eliminazione che si basano sulla decomposizione QR della matrice dei vincoli per eliminare alcune variabili e risolvere un problema equivalente di programmazione quadratica non vincolata di dimensioni più piccole. La stabilità numerica di un metodo di questa classe, il metodo di eliminazione diretta, viene studiata mediante la tecnica dell’analisi all’indietro dell'errore.

1997 - Error analysis of an algorithm for equality-constrained quadratic programming problems [Articolo su rivista]
Galligani, Emanuele; Zanni, Luca
abstract

In this paper the numerical stability of the orthogonal factorization method for linear equality-constrained quadratic programming problems is studied using a backward error analysis. A perturbation formula for the problem is analyzed; the condition numbers of this formula are examined in order to compare them with the condition numbers of the two matrices of the problem. A class of test problems is also considered in order to show experimentally the behaviour of the method.

1997 - Splitting methods and parallel solution of constrained quadratic programs [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

In this work the numerical solution of linearly constrained quadratic programming problems is examined. This problem arises in many applications and it forms a basis for some algorithms that solve variational inequalities formulating equilibrium problems. An attractive iterative scheme for solving constrained quadratic programs when the matrix of the objective function is large and sparse consists in transforming, by a splitting of the objective matrix, the original problem into a sequence of subproblems easier to solve. At each iteration the subproblem is formulated as a linear complementarity problem that can be solved by methods suited for implementation on multiprocessor system. We analyse two parallel iterative solvers from the theoretical and practical point of view. Results of numerical experiments carried out on Cray T3D are reported.

1997 - Splitting methods for quadratic optimization in data analysis [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

Many problems arising in data analysis can be formulated as a large sparse strictly convex quadratic programming problems with equality and inequality linear constraints. In order to solve these problems, we propose an iterative scheme based on a splitting of the matrix of the objective function and called splitting algorithm (SA). This algorithm transforms the original problem into a sequence of subproblems easier to solve, for which there exists a large number of efficient methods in literature. Each subproblem can be solved as a linear complementarity problem or as a constrained least distance problem. We give conditions for SA convergence and we present an application on a large scale sparse problem arising in constrained bivariate interpolation. In this application we use a special version of SA called diagonalization algorithm (DA). An extensive experimentation on CRAY C90 permits to evaluate the DA performance.

1997 - The two-stage arithmetic mean method [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero
abstract

In several recent works, the Arithmetic Mean Method for solving large sparse linear systems has been introduced and analysed. Each iteration of this method consists of solving two independent systems. When we obtain two approximate solutions of these systems by a prefixed number of steps of an iterative scheme, we generate an inner/outer procedure, called Two-Stage Arithmetic Mean Method. General convergence theorems are proved for M-matrices and for symmetric positive definite matrices. In particular, we analyze a version of Two-Stage Arithmetic Mean Method for T(q, r) matrices, deriving the convergence conditions. The method is well suited for implementation on a parallel computer. Numerical experiments carried out on Cray-T3D permits to evaluate the effectiveness of the Two-Stage Arithmetic Mean Method.

1996 - Error analysis of elimination methods for equality constrained quadratic programming problems [Relazione in Atti di Convegno]
Galligani, Emanuele; Zanni, Luca
abstract

A backward error analysis for the orthogonal factorization method for equality constrained quadratic programming problems has been developed. Furthermore, this method has been experimentally compared with direct elimination method on a class of test problems.

1996 - Quadratic optimization in data analysis [Capitolo/Saggio]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

Sono stati esaminati due approcci per la risoluzione di problemi derivanti dall’analisi dei dati. Il primo consiste nell’applicare una tecnica di substrutturazione che porta a dover risolvere un insieme di problemi di programmazione quadratica convessa con vincoli lineari di uguaglianza. Tali problemi sono indipendenti e possono essere risolti su processori diversi, usando per la soluzione di ciascuno di essi il metodo dei moltiplicatori combinato con l’algoritmo dei gradienti coniugati, particolarmente efficiente su un processore vettoriale.Per problemi con struttura più sparsa, quale quello dell’interpolazione vincolata di superfici di classe C1, si può usare un approccio globale, che richiede di risolvere un problema di programmazione quadratica strettamente convessa con vincoli di uguaglianza e disuguaglianza. In questo caso si è analizzata teoricamente una classe di metodi derivanti dalla decomposizione della matrice della funzione obiettivo. Una vasta sperimentazione numerica su Cray C90 mostra l’efficienza di uno di questi metodi, detto algoritmo di diagonalizzazione.

1996 - Solution of the Sylvester equation on a parallel computer [Relazione in Atti di Convegno]
Galligani, Emanuele
abstract

This paper is concerned with a parallel solution of the Sylvester matrix equation AX+XB=C by means of the iterative method of successive approximations. In this work convergence conditions for the method are given. If the matrices A and B have a block partitioned form, different choices of the splittings of A and B are presented. In this case at each iteration of the method, one has to solve a set of independent Sylvester equations, which can be solved in parallel by means of a direct method. By using the multisplitting principle it has been also introduced an explicit parallelism in the method. The implementation of the iterative method on a distributed memory system such as Cray T3D has been described and the results of some computational experiments related to the solution of the Riccati equation, have been presented.

1996 - Splitting methods for constrained quadratic programs in data analysis [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

This paper is concerned with the numerical solution of a linearly constrained quadratic programming problem by methods that use a splitting of the objective matrix. We present an acceleration step for a general splitting algorithm and we establish the convergence of the resulting accelerated scheme. We report the results of numerical experiments arising in constrained bivariate interpolation to evaluate the efficiency of this acceleration technique for a particular splitting of the objective matrix and for the corresponding extrapolated form.

1996 - The two-stage arithmetic mean method on Cray T3D [Capitolo/Saggio]
Galligani, Emanuele; V., Ruggiero
abstract

Il metodo della Media Aritmetica è particolarmente adatto per risolvere su sistemi multiprocessori sistemi lineari sparsi di dimensioni elevate con struttura a banda. Infatti ogni iterazione consiste nel risolvere due sistemi indipendenti diagonali a blocchi. Quando per le soluzioni di tali sistemi si calcolano solo delle approssimazioni mediante un numero prefissato di passi di uno schema iterativo, si genera una procedura detta metodo della Media Aritmetica a Due Stadi. Una serie di esperimenti numerici effettuati su Cray T3D permette di valutare l’efficienza di questo schema, evidenziandone le caratteristiche parallele.

1995 - Implementation of splitting methods for solving block tridiagonal linear systems on transputers [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero
abstract

This paper is concerned with the parallel implementation of two splittings methods for solving block tridiagonal linear systems on a transputer network. For both methods, we describe the data allocation, the workload distribution and the interprocessor communications and we evaluate the effectiveness of the two parallel algorithms by numerical experiments on a set of test problems.

1995 - The diagonalization method for strictly convex quadratic programs: analysis and implementationon vector computers [Working paper]
Galligani, Emanuele; V., Ruggiero; Zanni, Luca
abstract

This report concerns with the solution of linearly constrained strictly convex quadratic programming problem by a splitting iterative method, called diagonalization algorithm (DA). This algorithm transforms the original problem into a sequence of subproblems easier to solve, for which there exists a large number of efficient methods in literature. In fact each subproblem may be formulated as a linear complementarity problem or as a constrained least distance problem. We give conditions for DA convergence and we present an application on a large scale sparse problem arising in constrained bivariate interpolation. An extensive experimentation on CRAY C94 permits to evaluate the DA performance.The Fortran 77 codes carried out on multivector computer Cray C94 implementing the algorithms described above, are reported in appendix.

1994 - A parallel additive preconditioner for conjugate gradient method for AX+XB=C [Articolo su rivista]
D. J., Evans; Galligani, Emanuele
abstract

This paper is concerned with the solution of a linear system of equations which have the form of AX + XB = C by the preconditioned conjugate gradient (PCG) method. Such systems arise from finite difference discretization of separable elliptic boundary value problems on rectangular domains. A parallel additive preconditioner for the conjugate gradient (CG) method for solving such systems is presented. Some numerical experiments on the Poisson model problem are carried out on the Sequent Balance 8000 to evaluate the effectiveness of the additive preconditioner with respect to block diagonal preconditioners.

1994 - A parallel preconditioner for block tridiagonal matrices [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero
abstract

This paper is concerned with the solution of block tridiagonal linear algebraic systems by the preconditioned conjugate gradient (PCG) method. If we consider two splittings of the coefficient matrix, it is possible to derive a parallel additive polynomial preconditioner and to give conditions for such preconditioner to be symmetric positive definite. For the diffusion problem this preconditioner can be interpreted as a simple form of domain decomposition preconditioning. In order to solve each subdomain problem we analyse two solvers named Cyclic Reduction solver and Approximate Schur solver. Numerical results carried out on Cray Y-MP for a set of test-problems permit to evaluate the effectiveness of the parallel polynomial preconditioner.

1994 - A polynomial preconditioner for block tridiagonal matrices [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero
abstract

This paper is concerned with the solution of block tridiagonal linear systems by the preconditioned conjugate gradient (PCG) method. If we consider a block AGE splitting of the coefficient matrix, it is possible to derive an additive polynomial preconditioner and to give conditions for such preconditioner to be symmetric positive definite.Numerical experiments on diffusion problem are carried out on CRAY Y-MP in order to evaluate the effectiveness of the parallel polynomial preconditioner.

1994 - Analysis of splitting parallel methods for solving block tridiagonal linear systems [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero
abstract

This paper is concerned with the solution of block tridiagonal linear algebraic systems by two different parallel methods, the Arithmetic Mean method and the Alternating Group Explicit method. Similar convergence conditions hold for both methods. We describe the parallel implementation of both methods on shared and distributed memory systems and we report the results of numerical experiments on a set of test problems.

1994 - Error analysis of null space algorithm for linear equality constrained least squares problems [Articolo su rivista]
Galligani, Emanuele; A., Laratta
abstract

The numerical stability of the null space method for linear least-squares problems with linear equality constraints is studied using a backward error analysis. A class of test problems is also considered in order to show experimentally the behaviour of the method.

1994 - On the efficiency and numerical stability of orthogonal factorization method for equality-constrained quadratic programming problems [Working paper]
Galligani, Emanuele; Zanni, Luca
abstract

We consider the orthogonal factorization method for linear equality-constrained quadratic programming problems. Backward error analysis of this method is developed in a previous work. In this paper the efficiency and the numerical stability of the method are evaluated experimentally on a class of test problems. The computer experimentation is carried out on CRAY C90 using LINPACK library.

1994 - The arithmetic mean preconditioner for multivector computers [Capitolo/Saggio]
Galligani, Emanuele; V., Ruggiero
abstract

In this paper we consider the arithmetic mean preconditioner for the conjugate gradient method. This preconditioner is designed to be implemented on a multiprocessor system that can execute concurrently different tasks on vector processors.Some spectral bounds for the preconditioner have been obtained. A comparison between this preconditioner and the SSOR preconditioner has been carried out on different test-matrices. Also the m-step preconditioners generated by the arithmetic mean preconditioner and by the SSOR preconditioner have been compared.

1993 - A parallel preconditioner for block tridiagonal matrices [Working paper]
Galligani, Emanuele; V., Ruggiero
abstract

In this report we consider two parallel additive preconditioners for solving block tridiagonal linear algebraic systems by the preconditioned conjugate gradient (PCG) method. If we consider two different splittings of the coefficient matrix, the first suggested by Evans and others and the second by authors of this report, it is possible to derive two parallel additive polynomial preconditioners of order m and to give conditions for such preconditioners to be symmetric positive definite. A Fortran implementation of the PCG method on Cray Y-MP has been developed in order to evaluate the effectiveness of the considered polynomial preconditioners. The numerical results carried out with this program permit to analyse the two preconditioners with respect to the complexity and the accuracy.The Fortran 77 codes carried out on multivector computer Cray Y-MP implementing the algorithms above, are reported in appendix.

1993 - C1 surface interpolation with constraints [Articolo su rivista]
Galligani, Emanuele
abstract

Given n pairwise distinct and arbitrarily spaced points P_i in a domain D of the x-y plane and n real numbers f_i, consider the problem of computing a bivariate function f(x,y) of class C1 in D whose values in P_i are exactly f_i, i=1,...,n, and whose first or second order partial derivatives satisfy appropriate equality and inequality constraints on a given set of p points Q_l in D.In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires the solution of a large scale quadratic programming (QP) problem. The main purpose of this work is to analyse an iterative method for determining the solution of this QP problem: such a method is very efficient and well suited for parallel implementation on a multiprocessor system.

1993 - Il metodo della media aritmetica su sistemi multivettoriali [Capitolo/Saggio]
Galligani, Emanuele; V., Ruggiero
abstract

In questa relazione si riassumono i contenuti di una serie di pubblicazioni e di rapporti tecnici relativi agli anni 1990-93, riguardanti un progetto di analisi dell’idea della media aritmetica per la risoluzione di sistemi sparsi di grandi dimensioni su calcolatori multivettoriali. L’intera sperimentazione numerica è stata eseguita mediante lo sviluppo di codici Fortran per il sistema Cray.

1993 - The solution of nonlinear parabolic and hyperbolic equations by the AGE algorithms [Working paper]
Galligani, Emanuele; D. J., Evans
abstract

In this paper the finite difference method is applied to nonlinear parabolic and hyperbolic differential equations subject to initial and boundary value conditions. The resulting matrix system is solved by the alternating group explicit (AGE) method, the coupled AGE method and the reduced AGE method.

1992 - A new version of the arithmetic mean method for solving block tridiagonal linear systems [Working paper]
V., Ruggiero; Galligani, Emanuele
abstract

In this report we consider a new version of the arithmetic mean method for solving large block tridiagonal linear systems. The iterative method converges for systems with symmetric positive definite or positive real matrices or irreducible L-matrices with a strong diagonal dominance. When the coefficient matrix is symmetric positive definite, an additive preconditioner for the conjugate gradient method is derived.The Fortran 77 code carried out on multivector computer Cray Y-MP implementing the algorithm above, are reported in appendix.

1992 - A parallel algorithm for solving block tridiagonal linear systems [Articolo su rivista]
V., Ruggiero; Galligani, Emanuele
abstract

In this paper, we consider a new form of the arithmetic mean method for solving large block tridiagonal linear systems. The iterative method converges for systems with coefficient matrices that are symmetric positive definite or positive real or irreducible L-matrices with a strong diagonal dominance. When the coefficient matrix is symmetric positive definite, an additive preconditioner for the conjugate gradient method is derived.Both the iterative method and the preconditioner are very suitable for parallel implementation on a multivector computer. Some numerical experiments on systems resulting from the discretization of an elliptic partial differential equation are carried out on the CRAY-MP.

1992 - Computation of minimal eigenpair in the large sparse generalized eigen-problem using vector computers [Relazione in Atti di Convegno]
Galligani, Emanuele; V., Ruggiero
abstract

This paper is concerned with the computation of the minimal eigenpair of the generalized eigen-problem. An iterative method of first degree with the arithmetic mean preconditioner and the SSOR preconditioner has been analyzed. These preconditioners have been evaluated also for the method of Rayleigh quotient minimization.

1992 - The arithmetic mean preconditioner for multivector computers [Articolo su rivista]
Galligani, Emanuele; V., Ruggiero
abstract

In this paper we consider the arithmetic mean preconditioner for the conjugate gradient method. This preconditioner is designed to be implemented on a multiprocessor system that can execute concurrently different tasks on vector processors.Some spectral bounds for the preconditioner have been obtained. A comparison between this preconditioner and the SSOR preconditioner has been carried out on different test-matrices. Also the m-step preconditioners generated by the arithmetic mean preconditioner and by the SSOR preconditioner have been compared.

1991 - Computation of minimal eigenpair in the large sparse generalized eigen-problem using vector computer [Working paper]
Galligani, Emanuele; V., Ruggiero
abstract

This report is concerned with the computation of the minimal eigenpair of the generalized eigen-problem. An iterative method of first degree with the arithmetic mean preconditioner and the SSOR preconditioner has been analyzed. These preconditioners have been evaluated also for the method of Rayleigh quotient minimization.The Fortran 77 codes carried out on multivector computer Cray Y-MP implementing the algorithms described above, are reported in appendix.

1991 - Metodi di decomposizione di operatori [Capitolo/Saggio]
I., Galligani; V., Ruggiero; Galligani, Emanuele
abstract

In questa relazione si riassumono i contenuti di una serie di pubblicazioni e di rapporti tecnici relativi agli anni 1988-90, riguardanti il metodo della Media Aritmetica per la risoluzione di sistemi lineari di equazioni differenziali ordinarie, per la risoluzione di sistemi lineari di equazioni algebriche e come precondizionatore per il metodo dei gradienti coniugati.

1990 - An iterative method for large sparse linear systems on a vector computer [Articolo su rivista]
V., Ruggiero; Galligani, Emanuele
abstract

In this paper we consider the arithmetic mean method for solving large sparse systems of linear equations. This iterative method converges for systems with coefficient matrices that are symmetric positive definite or positive real or irreducible L-matrices with a strong diagonal dominance. The method is very suitable for parallel implementation on a multiprocessor system, such as the CRAY X-MP. Some numerical experiments on systems resulting from the discretization, by means of the usual 5-point difference formulae, of an elliptic partial differential equation are presented.