Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
2907
Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo
Ivan Lirkov Svetozar Margenov Plamen Yalamov
Large-Scale Scientific Computing 4th International Conference, LSSC 2003 Sozopol, Bulgaria, June 4-8, 2003 Revised Papers
Springer
eBook ISBN: Print ISBN:
3-540-24588-X 3-540-21090-3
©2005 Springer Science + Business Media, Inc. Print ©2004 Springer-Verlag Berlin Heidelberg Dordrecht All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.kluweronline.com http://www.springeronline.com
Preface
The papers in this volume were presented at the 4th International Conference on Large-Scale Scientific Computations ICLSSC 2003. It was held in Sozopol, Bulgaria, June 4–8, 2003. The conference was organized and sponsored by the Central Laboratory for Parallel Processing at the Bulgarian Academy of Sciences. Support was also provided from the Center of Excellence “BIS 21” (funded by the European Commission), SI AM and GAMM. A co-organizer of this traditional scientific meeting was the Division of Numerical Analysis and Statistics of the University of Rousse. The success of the conference and the present volume in particular are the outcome of the joint efforts of many colleagues from various institutions and organizations. First thanks to all the members of the Scientific Committee for their valuable contribution to forming the scientific face of the conference, as well as for their help in reviewing contributed papers. We would like to specially thank the organizers of the special sessions: R. Blaheta, N. Dimitrova, A. Ebel, K. Georgiev, O. Iliev, A. Karaivanova, H. Kosina, M. Krastanov, U. Langer, P. Minev, M. Neytcheva, M. Schäfer, V. Veliov, and Z. Zlatev. We are also grateful to the staff involved in the local organization. Special Events: The conference was devoted to the 60th anniversary of Raytcho Lazarov. During the conference, the nomination for the World Level of the Hall of Fame for Engineering, Science and Technology, HOFEST, was officially awarded to Owe Axelsson. Traditionally, the purpose of the conference is to bring together scientists working with large-scale computational models of environmental and industrial problems, and specialists in the field of numerical methods and algorithms for modern high-speed computers. The key lectures reviewed some of the advanced achievements in the field of numerical methods and their efficient applications. The ICLSSC 2003 talks were presented by university researchers and practical industry engineers, including applied mathematicians, numerical analysts and computer experts. The general theme for ICLSSC 2003 was Large-Scale Scientific Computing, focusing on: Recent achievements in preconditioning techniques; Monte Carlo and quasi-Monte Carlo methods; set-valued numerics and reliable computing; environmental modelling; large-scale computations for engineering problems. More than 90 participants from all over the world attended the conference, representing some of the strongest research groups in the field of advanced large-
VI
Preface
scale scientific computing. This volume contains 55 papers submitted by authors from over 20 countries, out of which 5 were invited and 50 were contributed. The 5th International Conference LSSC 2005 is planned for June 2005.
November 2003
Ivan Lirkov Svetozar Margenov Plamen Yalamov
Table of Contents
I
Invited Papers
Eigenvalue Estimates for Preconditioned Saddle Point Matrices Owe Axelsson A 3D Projection Scheme for Incompressible Multiphase Flows Using Dynamic Front Refinement and Reconnection Tong Chen, Peter Dimitrov Minev, and Krishnaswamy Nandakumar Schwarz-Like Methods for Approximate Solving Cooperative Systems Ivo Marek
3
17 25
Computational Infrastructure for Parallel, Distributed, and Grid-Based Monte Carlo Computations Michael Mascagni and Yaohang Li
39
Parallel Solution of Very Large Sparse Systems of Linear Algebraic Equations Zahari Zlatev
53
II
Recent Achievements in Preconditioning
Solution of Robust Linear Regression Problems by Krylov Subspace Methods Venansius Baryamureeba
67
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov
76
Parallel High Performance Computing on Composite Grids Roman Kohut
85
Parallel Preconditioning for Sedimentary Basin Simulations Roland Masson, Philippe Quandalle, Stéphane Requena, and Robert Scheichl
93
III
Monte Carlo and Quasi-Monte Carlo Methods
Modeling of Narrow-Width SOI Devices: The Role of Quantum Mechanical Narrow Channel Effects on Device Performance Shaikh S. Ahmed and Dragica Vasileska
105
VIII
Table of Contents
Monte Carlo Algorithm for Ballistic Object Tracking with Uncertain Drag Parameter Donka Angelova, Iliyana Simeonova, and Tzvetan Semerdjiev
112
Efficient CPU-Specific Algorithm for Generating the Generalized Faure Sequences Emanouil I. Atanassov
121
A New Quasi-Monte Carlo Algorithm for Numerical Integration of Smooth Functions Emanouil I. Atanassov, Ivan T. Dimov, and Mariya K. Durchova
128
Monte Carlo Method for Multiple Knapsack Problem Stefka Fidanova
136
Importance Separation for Solving Integral Equations Rayna Georgieva and Sofiya Ivanovska
144
A Parallel Monte Carlo Method for Electron Quantum Kinetic Equation Todor V. Gurov and Ivan T. Dimov
153
Solving BVPs Using Quasirandom Walks on the Boundary Aneta Karaivanova, Michael Mascagni, and Nikolai A. Simonov
162
A Stable Backward Monte Carlo Method for the Solution of the Boltzmann Equation Hans Kosina, Mihail Nedjalkov, and Siegfried Selberherr
170
A Weight Decomposition Approach to the Sign Problem in Wigner Transport Simulations Mihail Nedjalkov, Hans Kosina, and Siegfried Selberherr
178
A Zero Field Monte Carlo Algorithm Accounting for the Pauli Exclusion Principle Sergey Smirnov, Hans Kosina, Mihail Nedjalkov, and Siegfried Selberherr
IV
185
Set-Valued Numerics and Reliable Computing
Solution Methods for Age-Structured Optimal Control Models with Feedback Christian Almeder Multivariate Rational Interpolation of Scattered Data Stefan Becuwe, Annie Cuyt, and Brigitte Verdonk Approximation Methods for Nonconvex Parabolic Optimal Control Problems Using Relaxed Controls Ion Chryssoverghi
197 204
214
Table of Contents
Stabilizing Feedback of a Nonlinear Biological Wastewater Treatment Plants Model Neli Dimitrova and Mikhail Krastanov Higher Order Approximations of Affinely Controlled Nonlinear Systems Nikolay Kirov and Mikhail Krastanov Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity Vladik Kreinovich, Luc Longpré, Praveen Patangay, Scott Ferson, and Lev Ginzburg
IX
222 230
238
On the Approximation of Centered Zonotopes in the Plane Svetoslav Markov and Dalcidio Claudio
246
On Range Evaluation of Polynomials by Applying Interval Arithmetic Shinya Miyajima and Masahide Kashiwagi
254
262 Sharp Bounds for Strains and Stresses in Uncertain Mechanical Models Evgenia D. Popova, Maria Datcheva, Roumen Iankov, and Tom Schanz
One Approximation to the Reachable Sets of Strongly Convex Differential Inclusions Nedka Pulova and Vladimir Pulov Robust Methodology for Characterizing System Response to Damage: Approach Based on Partial Order Paul J. Tanenbaum, Carlos de la Mora, Piotr Wojciechowski, Olga Kosheleva, Vladik Kreinovich, Scott A. Starks, and Alexandr V. Kuzminykh
V
270
276
Environmental Modelling
Comparison of Two Local Refinement Methods for Large Scale Air Pollution Simulations Anton Antonov, Krassimir Georgiev, Emilia Komsalova, and Zahari Zlatev Testing Weighted Splitting Schemes on a One-Column Transport-Chemistry Model Mike Botchev, István Faragó, and Ágnes Havasi Long-Range Transport of Dust to the Baltic Sea Region Marke Hongisto and Mikhail Sofiev Atmospheric Dispersion and Pollutant Chemical Transformation Simulated with Parallel Calculation Using a PC Cluster Christelle Philippe, Alexis Coppalle
287
295 303
312
X
Table of Contents
A Mesoscale Study of Large Industrial Emission Impact over Madrid Mesoscale Domain by Using MM5-CMAQ Modelling System Roberto San José García, Juan Luis Pérez Camaño, Raul Priego, and Rosa M. González Barras
320
Study of the Pollution Exchange between Bulgaria and Northern Greece 328 Christos Zerefos, Dimiter Syrakov, Kostadin Ganev, Alexandros Vasaras, Kostas Kourtidis, Maria Tzortziou, Maria Prodanova, Reneta Dimitrova, Dimiter Yordanov, and Nikolai Miloshev Studying High Ozine Levels in Bulgaria and Europe Zahari Zlatev and Dimiter Syrakov
VI
337
Large Scale Computation for Engineering Problems
Collocation Methods for Boundary Value Problems with an Essential Singularity Winfried Auzinger, Othmar Koch, and Ewa Weinmüller
347
Boundary Integral Method for Deformable Interfaces in the Presence of Insoluble Surfactants Ivan B. Bazhlekov, Patrick D. Anderson, and Han E.H. Meijer
355
Large Eddy Simulation of Turbulent Square Channel Flow Using a PC-Cluster Architecture Jordan Denev, Thomas Frank, and Klaus Pachler
363
Adaptive Grid Refinement for Computation of the Homogenized Elasticity Tensor Ronald H. W. Hoppe, Svetozara I. Petrova, and Yuri V. Vassilevski
371
Multigrid Preconditioned Solvers for Some Elastoplastic Problems Johanna Kienesberger
379
The Free Transmission Problem for a Water Droplet Dirk Langemann
387
Numerical Simulation of the Flow in Magnetic Fluid Rotary Shaft Seals Teodora Mitkova and Lutz Tobiska
396
Phase-Field Method for 2D Dendritic Growth Vladimir Slavov, Stefka Dimova, and Oleg Iliev
404
Design of 2-D FIR Digital Filters Using a Parallel Machine Felicja Wysocka-Schillak
412
Table of Contents
VII
XI
Contributed Talks
Parallel Performance Comparison of Three Direct Separable Elliptic Solvers Gergana Bencheva
421
Finite Volume Difference Methods for Convection-Dominated Problems with Interface Iliya A. Brayanov and Lubin G. Vulkov
429
Parameter Estimations in Nonlinear Parabolic Systems with Time Delay Gabriel Dimitriu and
438
Systolic Architecture of Adaptive Post Detection Integration CFAR Processor in Binomial Distribution Pulse Jamming Ivan Garvanov, Christo Kabakchiev, and Plamen Daskalov
448
Immersed-Boundary Level Set Approach for Numerical Solution of Elliptic Interface Problems Juri D. Kandilarov
456
Generalized Nonstandard Numerical Methods for Nonlinear Advection-Diffusion-Reaction Equations Hristo V. Kojouharov and Bruno D. Welfert
465
On the Computation of Blow-Up Solutions of Elliptic Equations with Semilinear Dynamical Boundary Conditions Miglena N. Koleva
473
A Method for Solving Hermitian Pentadiagonal Block Circulant Systems of Linear Equations 481 Borislav V. Minchev and Ivan G. Ivanov
Author Index
489
This page intentionally left blank
Part I
Invited Papers
This page intentionally left blank
Eigenvalue Estimates for Preconditioned Saddle Point Matrices Owe Axelsson University of Nijmegen, Nijmegen, The Netherlands
[email protected]
Abstract. Eigenvalue bounds for saddle point matrices on symmetric or, more generally, nonsymmetric form are derived and applied for preconditioned versions of the matrices. The preconditioners enable efficient iterative solution of the corresponding linear systems.
1
Introduction
Matrices on saddle point form arise in constrained problems which in various forms occur in applications such as in constrained optimization, flow problems for incompressible materials, and domain decomposition methods, to name a few. For large scale such problems iterative methods must be used and require then efficient preconditioners. We derive first bounds on the eigenvalues of symmetric forms of saddle point matrices, showing how they depend on the top matrix block and the Schur complement matrix. The bounds are then improved using a congruence transformation of the matrix, which makes the off-diagonal matrices small. The transformation is followed by a block-diagonal preconditioner. It is seen that the off-diagonal blocks have only a second order influence on the resulting eigenvalue bounds, and the eigenvalues depend mainly only on the preconditioned top matrix and negative Schur complement matrix, which, by assumption, both have positive eigenvalues. The eigenvalues of the resulting preconditioned matrix are real and cluster around – 1 and +1. A corresponding form of transformation can be applied for nonsymmetric matrices. One source of nonsymmetry can be due to a shift of sign of the constrained equations and we show in this case how the eigenvalues of the preconditioned matrix cluster around the unit number in the complex plane. The preconditioned matrix problems can be solved using a generalized minimal residual form of the conjugate gradient method. For intervals symmetrically located around the origin, the effective condition number equals the square of the condition number for each of the two intervals, showing the importance of having preconditioned the matrices to have intervals with sufficiently small condition numbers. For problems where the matrix defining the constraint is (nearly) rank deficient or, equally, the corresponding term in the Schur complement matrix has a zero or small eigenvalues, one can apply a regularization technique to stabilize the smallest eigenvalue. Such methods have been used in [1,3], for instance. I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 3–16, 2004. © Springer-Verlag Berlin Heidelberg 2004
4
Owe Axelsson
The present method is applicable also for nonsymmetric problems on saddle point form. Here the top matrix block is strongly nonsymmetric when it originates from a convection dominated convection diffusion problem, for instance. For such problems it is important to use a discretization method which leads to nearly M-matrices enabling a efficient preconditioning, in particular if a proper node ordering based on the directions of the flow field has been used. Examples of such methods can be found in [4] and [5], for instance. Some of the above estimates have previously been derived in [6]. See also other references cited there. In the present paper the estimates of eigenvalue bounds for the preconditioned matrices are derived from the general estimates for matrices on saddle point form. In particular, they generalize the methods presented in [6, 7] and elsewhere, where the preconditioning matrix itself has a saddle point form but is factorized in block triangular factors.
2
Eigenvalues of Matrices on Saddle Point Form
Given
where M of order
is symmetric and positive defi-
nite, C of order is symmetric and it is assumed that the negative Schur complement matrix is positive definite. Note that if C = 0, the latter assumption implies that and B has full
Let be the eigenvalues of M be the eigenvalues of can be factored as
where
are corresponding unit matrices, that is, it can be written as a con-
gruence transformation of
Since, by assumption, the latter matrix is
indefinite and since, by Sylvester’s theorem, congruence transformations preserve the signs of the eigenvalues it follows that is indefinite and also nonsingular, because both M and S are nonsingular. We shall compute intervals that contain the eigenvalues of Being symmetric and indefinite, the eigenvalues of are real and located on both sides of the origin. The next theorem shows bounds for the eigenvalue intervals. Theorem 1. Let
where M and
metric and positive definite. Let be the eigenvalues of M and the spectral radius. Then
are symrespectively, and let
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
(a) The eigenvalues
of
5
are located in the two intervals
(b) If C is positive semidefinite then the upper bound can be replaced by the more accurate bound
(c) If C = 0 and B has full row rank, then
Proof. Let be an eigenpair of rewrite this eigenvalue problem in the form
or, with
i.e.,
in the form
This is further rewritten in the form
or
Since is nonsingular, it holds that Given an eigenpair, we consider the two cases, (i) (ii) separately. (i) In this case is nonsingular and (2) reduces to
We
6
Owe Axelsson
or where Hence
Since
(ii)
it follows that
In this case
is nonsingular and (2) reduces to
or
so Since now
it follows that
that is
Here
where Therefore, by (3)
This proves part (a). For parts (b) and (c) we use (1), which for to
or Let
Since
it holds that
and it follows that
reduces
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
7
For C = 0, we have It holds
or
Therefore, since
where if C = 0, otherwise It only remains to prove the bounds for the negative eigenvalues for the case C = 0. It follows from (4) and (5),
where For
we get the solution
which, since
shows the stated bounds for C = 0.
Corollary 1. The eigenvalues of the block-diagonal preconditioned matrix are contained in the intervals where definite. Proof. Replace S with
Here and M with
if C is positive semi-
in Theorem 1.
Remark 1. The above bounds are more accurate than previously given bounds in [8] and [9]. In addition, they hold even if C is not positive semi-definite. An important observation from Theorem 1 is that the negative eigenvalues depend essentially only on S while the positive eigenvalues depend essentially only on M. If M is well-conditioned, the eigenvalue bounds are most sensitive to the values of and Frequently is bounded by a not very big number but can take small values if B is nearly rank-deficient and C does not compensate for this.
8
2.1
Owe Axelsson
Improvement of Eigenvalue Bounds by Congruence Transformation
We show now how the eigenvalue bounds of a given matrix on saddle point form can be improved by a congruence transformation for a proper block triangular matrix Z. Since, by Sylvester’s theorem, a congruence transformation preserves the signs of the eigenvalues, as is seen from Corollary 1, the aim is here to cluster the eigenvalues around the points –1 and +1. Let then be an approximate inverse of M and let
Then a computation shows that
Here –S, where is the Schur complement of It is readily seen that this also equals the Schur complement of Therefore, applying Theorem 1 for with B replaced by shows that the eigenvalues of are contained in the intervals
where accurate preconditioner to approximately in the intervals
When is a sufficiently it follows that the eigenvalues are contained
where the perturbations are of second order. Applying now proper symmetric and positive definite preconditioners and of S will shrink the intervals to (approximately)
of M
where are the extreme eigenvalues of and where The matrix can be a sparse matrix, possibly just diagonal, if it suffices to make small. We can also apply a more accurate preconditioner, such as The most sensitive part in the preconditioning is determined by which is small if B is nearly rank deficient and the matrix C does not stabilize, i.e. compensate for this defect. See further Section 4 for comments on this.
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
9
Block-Diagonal Preconditioner; Computational Complexity To compute the action on a vector
of the preconditioned matrix two actions of
and one of
where and
take
place, in addition to some matrix vector multiplications and vector additions. For the choice it suffices with two actions of the following algorithm is used:
(i) (ii) (iii) (iv) (v)
2.2
and one of
if
Solve Solve Compute Compute Solve
Iteration Number Bounds
The preconditioned saddle-point system can be solved by a generalized conjugate gradient-minimal residual method (see e.g. [2] ), which are based on the best approximations in the Krylov subspace
where is the preconditioner and for a given initial vector For symmetric matrices, the rate of convergence of such methods can be estimated by a best polynomial approximation, namely for some norm it holds
where is the set of eigenvalues of B and denotes the set of polynomials of degree normalized at the origin. For matrices with eigenvalues located symmetrically about the origin in intervals of equal length, it follows that the best polynomial approximation takes the form
which corresponds to a condition number that is, the square of the condition number for a single interval. For non-equal length intervals better bounds can be derived, but the above shows that it is important to precondition both S and M so that the condition number of each interval is not too large. It also shows that there are good reasons to look for preconditioning methods which transforms the eigenvalues to the positive halfplane, which we now consider.
10
Owe Axelsson
3 Clustering the Eigenvalues around the Unit Number in the Complex Plane Instead of using a preconditioner which clusters the eigenvalue around the points –1,+1 on the real axis, it can be more efficient to precondition the matrix to cluster the eigenvalues around the unit number in the complex plane. Applying the congruence transformation in (6), we change then the sign in the lower block part of the matrix and precondition it with a block diagonal matrix,
where
are symmetric and positive definite. The
corresponding eigenvalue problem takes then the form
which can be rewritten in the form
where To find the relative perturbations of the eigenvalues from those of matrix in (7) is rewritten in the form
and
the
where Here (8) shows that there is a perturbation of the real part with and of the imaginary part, arising from the skew symmetric part of the matrix, of It can be seen that if the eigenvalues are contained in an ellipse symmetrically located on the positive real axis, with eccentricity (that is, ratio of the semi axes), then the convergence factor which holds for a real interval is multiplied by the factor
(see e.g. [2]). The importance of having a narrow ellipse,
where are the foci of the ellipse, is seen. For applications in partial differential equation problems, where M is nonsymmetric (such as arising from a convection-diffusion problem) using discretization methods which leads to matrices M which are nearly M-matrices, enables the construction of accurate preconditioners to M. We show now how such preconditioners cluster the eigenvalues near the eigenvalues of The method is applicable also for nonsymmetric matrices.
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
3.1
11
A General Preconditioning Technique
Consider a nonsingular and in general nonsymmetric matrix, partitioned in twoby-two block form,
where has order We assume that is diagonalizable, i.e., has a complete eigenvector space and that is nonsingular. The most important application we have in mind is when is a matrix of regularized saddle point form, in which case is zero or negative semidefinite. When the given matrix is indefinite, we may transform it by multiplying the matrix rows for the bottom blocks by (–1). In this case the form is typically
where now the block matrix consists of a block diagonal part and a skewsymmetric off-diagonal part. The matrix M may be nonsymmetric. We shall present a general block incomplete factorization method for which enables clustering of eigenvalues of the preconditioning matrix around the unit number or around +1 and – 1, depending on the signs of certain matrices. Let then be nonsingular matrices of orders consistent with this partitioning and let
Let further
Here is a preconditioner to for instance an incomplete factorization, and is a preconditioner to the Schur complement matrix (see below for an explanation of these choices). will be used as a preconditioner to either as a left preconditioner or in the form which latter matrix is similarly equivalent to A computation shows that
The matrix
can be rewritten in the form
12
Owe Axelsson
where It follows from (10) that in order for to be an accurate preconditioner of must be an accurate preconditioner of and an accurate preconditioner of The accuracies of these approximations will be made precise in the next theorem. We need then the following (elementary) result. Lemma 1. It holds
where Proof. Let
There holds
where
and a computation shows that Theorem 2. Let
be preconditioned by
in (9), where
is a nonsingular preconditioner to and is a nonsingular preconditioner to Then, for a sufficiently accurate preconditioner the eigenvalues of the block preconditioned matrix cluster around unity and around the eigenvalues of where Namely, by a proper ordering of the eigenvalues it holds where
and Proof. Take norms in the second term of (11) and use Lemma 1. The theorem shows that we can control the clustering of the eigenvalues to be sufficiently close to unity and to the eigenvalues for by applying a sufficiently accurate preconditioner to These two approximations can be controlled, essentially independently of each other, the only dependence is that involves the inverse of the first preconditioner. Note that for saddle point matrices we may have eigenvalues with positive or negative real parts, depending on if the initial the transformation to the form has taken place, or not.
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
3.2
13
One-Sided versus Two-Sided Preconditioners
When dealing with iterative methods for nonsymmetric matrices an additional complication arises in that the matrix may not be normal, i.e., not symmetrizable. This means appearance of Jordan blocks, which can delay the rate of convergence substantially, or cause convergence stagnation. We discuss this issue in connection with one-sided versus two-sided preconditioners. Consider then the factorization of a nonsingular matrix
i.e.
Let be a preconditioner to and to for a left-sided, i.e. block Gauss-Seidel preconditioner it holds
Then
Now, even if is an accurate preconditioner to or, even if the presence of the upper off-diagonal matrix in the second factor in (12) may cause a delay or stagnation in the convergence of an iterative solution method. If
since then
it follows that the
minimal polynomial to is just i.e. has degree 2 and the convergence bound in section 2.2 shows that the GCG – MR method converges in just two iterations. However, in practice we have only approximations of and and the degree of the minimal polynomial is the equal or close to the order of the whole system rather than 2. In addition, the norms of the matrix powers
which arise in a Krylov method, can grow
rapidly with increasing number of iterations, causing perturbations and loss of orthogonality among the direction vectors in the minimal residual method. Numerical test show also a strong dependence on the preconditioning accuracy, in particular of to M. For reasons of robustness of an iterative method, it is therefore advisable to use a two-sided preconditioner, where the powers of the corresponding factors grow little. The one-sided preconditioner still involves actions of matrices and which is normally the computationally most expensive part in each iteration step, and little is saved compared to using a two-sided preconditioner, while the latter normally gives much fewer iterations.
14
4
Owe Axelsson
Regularization of (Nearly) Rank Deficient Problems
In finite element analysis the so-called Babuška-Brezzi (BB) condition, which is an inf sup condition, is commonly used to analyse the stability of constrained boundary value problems. This condition can be presented in algebraic form as follows. As we shall see, it is related to the smallest eigenvalues of the Schur complement matrix. Let B be of order where and rank First recall that the MoorePenrose generalized inverse of B equals The algebraic form of the BB condition is
Here, given
the sup is taken for
(or its scalar multiple), for which
We have
Hence, it follows that
Similarly, we obtain for the M-norm of
where M is spd,
Here if B has full rank but if B is rank deficient. If B is (nearly) rank deficient, one must regularize the problem, writing it in the form
Here the right-hand side term can sometimes be computed from the given problem as for Stokes problems or, otherwise, it is treated in a defect-correction way, i.e. with some initial approximation one computes a correction from
which may be repeated ones a number of times using the updated solutions.
Eigenvalue Estimates for Preconditioned Saddle Point Matrices
15
The matrix C is symmetric and positive semidefinite and positive definite on the nullspace of For the corresponding Schur complement it holds then
For the BB-condition to hold in finite element problems one must use stable element pairs for the two variables (such as velocity and pressure). This means that the space V for (velocity) must be sufficiently richer than that (W) for (pressure). For the simplest piecewise linear finite elements one can add bubble functions to V to form W. On the other hand, when finite element methods are implemented on parallel computer platforms, the data communication is simplified if one uses equal order finite elements for V and W. To stabilize for this, or to increase the stabilization even when one uses some stable element pairs, but where the constant is too small, one must use a stabilization term for some proper scalar The stabilization term should be active for the functions which are missing in an equal order finite element method compared to that for a BB-stable method. As such functions are of bubble type, they correspond to oscillating functions for which the choice the Laplacian operator is active and gives large perturbations On the other hand, the size of the coefficient must be sufficiently small in order not to perturb the discretization order of the method. This indicates that is a proper choice. This has been shown for the Stokes problem in [3]. Here, taking the divergence of the first equation using the incompressibility
results in the equation,
which, multiplied by a constant
gives
and corresponds to the regularization term
Similar choices can hold for more general problems, see e.g. [6]. However, the form of the regularization term is problem dependent.
5
Concluding Remarks
It has been shown how saddle point problems can be solved efficiently by iterative solution methods using particular preconditioners. Thereby it is important to precondition both the top-block matrix and the Schur complement matrix
16
Owe Axelsson
accurately, to achieve a method requiring few iterations. Stabilization is necessary to increase the smallest eigenvalue of the Schur complement matrix, when the constraint condition matrix is singular or nearly singular. In particular, it enables the use of simpler (equal order) finite elements in certain incompressible material problems (see [3] ). A way to make it possible to accurately precondition the top matrix block when it arises from convection diffusion problems is to use a discretization method for which the arising matrix ( M ) is an M-matrix. Here incomplete factorization methods results in accurate factorizations if a node ordering based on the local flow directions is used, see [5] for an example where block matrix factorizations have been used.
References 1. Axelsson, O.: Preconditioning of indefinite problems by regularization. SIAM Journal on Numerical Analysis 16 (1979) 58–69. 2. Axelsson, O.: A generalized conjugate gradient, least squares method. Numerische Mathematik 51 (1987) 209–227. 3. Axelsson, O., Barker, V.A., Neytcheva, M., Polman, B.: Solving the Stokes problem on a massively parallel computer. Mathematical Modelling and Analysis 4 (2000) 1–22. 4. Axelsson, O., Marinova, R.: A hybrid method of characteristics and central difference method for convection-diffusion problems. Computational and Applied Mathematics 21 (2002) 631–659. 5. Axelsson, O., Eijkhout, V., Polman, B., Vassilevski, P.: Iterative solution of singular perturbation 2nd order boundary value problems by use of incomplete block-matrix factorization methods. BIT 29 (1989) 867–889. 6. Axelsson, O., Neytcheva, M.: Preconditioning methods for linear systems arising in constrained optimization problems. Numerical Linear Algebra with Applications 10 (2003) 3–31. 7. Peruggia, I., Simoncini, V.: Block-diagonal and indefinite symmetric preconditioners for mixed finite element formulations. Preconditioning techniques for large sparse matrix problems in industrial application. Numerical Linear Algebra with Applications 7 (2000) 585–616. 8. Rusten, T., Winther, R.: A preconditioned iterative method for saddle point problems. SIAM J. Matrix. Anal. Appl. 13 (1992) 887–904. 9. Wathen, A., Silvester, D.: Fast Iterative Solution of Stabilized Stokes Systems Part II: Using General Block Preconditioners. SIAM Journal on Numerical Analysis 31 (1994) 1352–1367.
A 3D Projection Scheme for Incompressible Multiphase Flows Using Dynamic Front Refinement and Reconnection Tong Chen1, Peter Dimitrov Minev2, and Krishnaswamy Nandakumar1 1
Department of Chemical and Materials Engineering University of Alberta, Edmonton, Alberta, Canada T6G 2G6 2 Department of Mathematical and Statistical Sciences University of Alberta, Edmonton, Alberta, Canada T6G 2G1 {tc8,minev,kumar.nandakumar}@ualberta.ca
Abstract. This paper presents a 3D finite element method for incompressible multiphase flows with capillary interfaces based on a (formally) second-order projection scheme. The discretization is on a fixed reference (Eulerian) grid with an edge-based local The fluid phases are identified and advected using a level set function. The reference grid is then temporarily reconnected around the interfaces in order to maintain optimal interpolations accounting for the singularities. This method is simple and efficient, as demonstrated by the numerical examples on several free-surface problems.
1
Introduction
Multiphase flows, including the free-surface flows and bubbly flows, occur in a wide range of geophysical, chemical and industrial processes. Among them are oil transportation, mixing in chemical reactors, cooling of nuclear reactors, aeration processes, film coating, plastic molding and biomechanics. In general, it seems that it is more efficient to solve such problems in an Eulerian reference frame rather than in a Lagrangian or Eulerian-Lagrangian framework. There are numerous techniques based on the Eulerian approach and the reader is referred to the recent and comprehensive reviews by Scardovelli and Zaleski (1999) for the volume-of-fluid method, Osher and Fedkiw (2001) for the level-set method, and Tryggvason et al. (2001) for the front-tracking method. The difficulties with multiphase flow simulations are mostly due to the singularities (discontinuous pressure and normal derivatives of velocity) across the time-dependent free boundaries. At present, the most popular way to deal with the singularities at the interface, particularly in the finite difference context, is an approach based on a regularization of the using trigonometric approximation. However, such methods are at best only first-order accurate in space. The finite element method (FEM) for free-boundary problems has also undergone rapid development. Minev at el. (2003) have presented a 3D finite element technique based on a dynamic basis enrichment for pressure and velocity in Taylor-Hood I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 17–24, 2004. © Springer-Verlag Berlin Heidelberg 2004
18
Tong Chen, Peter Dimitrov Minev, and Krishnaswamy Nandakumar
elements. In 2D, a simple but efficient projection scheme has been proposed by the authors (Chen et al., 2003). In the present paper, we extend this scheme to 3D and demonstrate its capabilities on several difficult numerical examples.
2
Mathematical Formulation
We consider a 3D flow domain that contains two different Newtonian fluids and with constant densities and viscosities The fluids are assumed to be homogeneous, immiscible and incompressible, and separated by an interface In each single-phase domain the fluid motion is governed by the Navier-Stokes equations which, in a Cartesian coordinate system with the pointing opposite to gravity, read (in a stress-divergence form)
where the hydrodynamic pressure is the total pressure minus the hydrostatic pressure are the velocities and is the gravity acceleration, is the deviatoric stress with being the rate-of-strain tensor. Without the loss of generality, we assume Dirichlet boundary conditions on the external boundary Based on the classical hypothesis that the surface tension is proportional to the mean curvature of the balance of the total stress and the domain continuity results in the well-known interfacial conditions: Here, I is the identity tensor. [·] represents the jump at between the limiting values from the two sides of is the unit vector normal to pointing towards from and is the coefficient of surface tension. The mean curvature is The fluid properties are identified using a continuous indicator function that satisfies It is convenient though if the fluid interface
The normal direction to
3
is given by
corresponds to
so that
at
Discretization
With the time discretization, the Navier-Stokes equations in each of the singlephase domain can be split into a pure convection problem and a generalized
A 3D Projection Scheme for Incompressible Multiphase Flows
19
Stokes problem. In the present study, the former is solved using the AdamsBashforth method and the latter is tackled with the second-order projection scheme of Kim and Moin (1985). Starting at time level where the linearized fractional substeps are summarized as
Here, is the convected velocity. pressure by
is an auxiliary variable related to the
which is never explicitly computed. The free-surface boundary condition (2.2a) is split into and as discussed by Chen et al. (2003). The weak formulation of (3.1a) is trivial and therefore we present only the formulations of the split generalized Stokes problem (3.1b-d), with the special treatment for the interfacial boundary conditions. Let us choose, in each of the single-phase domain the test functions for the velocity and the test functions for the pressure Then the Galerkin formulations for (3.1b,c) and the for (3.1d) yield, respectively
The projection step (3.3c) makes the scheme equivalent to one of the stabilized schemes (at least in case of a single-phase flow) discussed by Codina (2001) and therefore allows for the use of an equal-order approximation for the pressure and velocity (see also Chen et al., 2003). The spatial discretization is performed on a fixed, Eulerian finite element grid (reference grid) which, however, is locally adapted (working grid) at each time step so that the interface is always aligned with element faces i.e. it never crosses the interior of a finite element of the working grid at any given discrete time instant An element on the reference grid that intersects with the interface and is to be reconnected to construct the working grid is called a front element. Furthermore, the basic reference grid can be refined prior to the adjustment of element faces with the interface. The pressure is double valued
20
Tong Chen, Peter Dimitrov Minev, and Krishnaswamy Nandakumar
in the nodes of the interface to account for its jump. We use approximation for the velocity space on the working grid, which automatically accounts for the discontinuity of the first derivatives of velocity. Equation (3.1a) as well as the equation (2.5) for the indicator are discretized on the reference grid while (3.1b-d) are discretized on the working grid. Let be the shape function for the velocity, and for the pressure, corresponding to a point The subscript denotes a discrete quantity and by definition
Imposing the condition
the unified weak formulation (3.3a) becomes
Here, is subject to the external boundary condition With which is a direct consequence of the weak formulation (3.3b) reads
and
Equation (3.5) contains two degrees of freedom for the pressure at each node that belongs to One of them can be condensed using the boundary condition
which appears to be a periodic-like boundary condition corresponding to the two fluids in and Here, is given by
due to (3.2). We can compute pointwise as explained later. Let us consider one interface node, J, and denote by are all the nodes linked to J through the elements containing J, including J itself. Let also be the subset of belonging to from Substituting (3.6) into (3.5) for node J so as to eliminate (condense) the values from we end up with
Likewise, we can obtain the discrete formulation for (3.3c) with the help of
A 3D Projection Scheme for Incompressible Multiphase Flows
21
of which the right-hand side can also be rewritten similar to (3.7):
In summary, equations (3.4), (3.7) and (3.8) form the unified algebraic system for the generalized Stokes problem on Obviously, it reduces to a conventional single-phase flow solver on either the reference grid or the working grid when For the purpose of pressure condensation, we need to evaluate the jump pointwise in all the nodes J on This is obtained by a localized least squares method as explained in Chen et al. (2003). Local refinement of mesh is a powerful tool for reducing the computational cost, especially in three dimensional and multiphase flow simulations where most effects are concentrated around the free interface. We applied the local technique (Ruprecht and Heinrich, 1998) to the front elements and their immediate neighbouring elements of the basic reference mesh. It is an edgebased subdivision of tetrahedron, very fast for time-dependant problems if the permanent edge information is stored prior to the time marching. The refinement is conformal in the sense that all hanging nodes are avoided according to the built-in templates. The values of a mid-edge (inserted) node will be inherited from the previous time level if it is refined previously; otherwise, linear averaging is applied. The identification of the front elements on the reference mesh is straightforward because in such elements the level set function would change sign in two vertices of an edge. Any variable to be interpolated at including the position of intersection can be determined using the linear finite element interpolant of along the edge (say, AB):
where It introduces dynamically new degrees of freedom to the system for both the velocity and pressure along the interface Generally, the interface (a plane in a linear tetrahedron) will cut the element, as shown in Fig. 1, in two configurations. In case (a) the tetrahedron is cut into one tetrahedron and one prism, while in case (b) it is cut into two prisms. Each of the prisms is further subdivided into three tetrahedra by trying to use the better diagonal combinations of the quadrilateral faces without violating the connectivity rules. Since these are the most common situations, the algorithm is dramatically simplified if it is not allowed that the intersection coincides with a vertex of the front element and then these would be the only two possible situations left. This restriction is enforced in the following manner. If the distance between on edge AB and its closest vertex (A/B) is smaller than a preset minimum allowable distance, then this point is fictitiously moved away from this vertex (without resetting on this distance along the edge. This is done by limiting where is a small positive number less than one half. This deviation introduces an error in the approximation of the zero-th level set,
22
Tong Chen, Peter Dimitrov Minev, and Krishnaswamy Nandakumar
Fig. 1. Reconnection of the front elements (pressure is double valued at intersection points 5, 6, 7, 8). The prism is further subdivided into three tetrahedra by linking the shorter diagonals of the quadrilateral faces. which is consistent with the overall accuracy of the method. for all the examples presented here.The choice of can affect the quality of the grid and therefore different values may be recommendable for other physical situations.
4
Numerical Examples
The present technique was quantitatively verified using the problem for bubble oscillation in a low-viscosity and initially quiescent liquid at zero gravity. We performed three tests starting with an initially ellipsoidal bubble whose volume is equal to that of a sphere of radius R = 0.5. The problem was solved in 1/8 of the domain by imposing symmetric conditions on the axis planes. The basic reference grid used for these simulations was a uniform grid containing uniform cubes, each subdivided into 6 tetrahedra. The dynamic gives an effective resolution of nodes. The densities were chosen to be and the viscosities, and The surface tension coefficients in the three cases were 0.5 and 0.2 correspondingly. The computed periods of oscillation are 0.81, 1.15 and 1.83 correspondingly, and they agree well with the classical potential flow results of Lamb (1932): 0.79, 1.11 and 1.76. The next testcase is about the Rayleigh-Taylor instability in a three dimensional rectangular box with a square horizontal cross section. The height-width aspect ratio was fixed at H = 4W. In order to compare our results with those of He et al. (1999), the surface tension was neglected and the viscosities were chosen to be the same for both the heavy and the light fluids. We solve the 1/4 domain symmetric with respect to the and planes. Periodic bound-
A 3D Projection Scheme for Incompressible Multiphase Flows
23
ary conditions were applied at the four vertical sides, while no-slip boundary conditions were applied at the top and bottom walls. The instability develops from the imposed single-mode initial perturbation
at 3/4 of the height above the bottom. The parameter setting is and which gives effectively an Atwood number a Reynolds number and a Froude number Fr = 1. The domain was resolved with the basic reference grid 16 × 16 × 128 nodes in right-angle tetrahedra. The effective local (around the interface) resolution is doubled after the one-level The interface evolution as the fluids penetrate each other is presented in Fig. 2. It is seen that the heavy fluid falls down in a relatively narrow “spike” forming a mushroomshaped end while the lighter fluid rises upward as a large “bubble”. The existence of four “saddle points” at the middle of the vertical sides distinguishes it from a two-dimensional Rayleigh-Taylor instability. In Fig. 3 we present the time evolutions of the spike tip, bubble front and the saddle point. The data correlate favourably with the higher-resolution (128 × 128 × 512, full domain) parallel computations of He et al. (1999) using the lattice Boltzmann method.
Fig. 2. Evolution of the fluid interface due to the Rayleigh-Taylor instability from a single-mode perturbation (At = 0.5, Re = 1000, Fr = 1).
24
Tong Chen, Peter Dimitrov Minev, and Krishnaswamy Nandakumar
Fig. 3. Positions of the bubble front, spike tip and saddle point versus time (At = 0.5, Re = 1000 ,Fr= 1).
References 1. Chen, T., Minev, P.D. and Nandakumar, K.: A projection scheme for incompressible multiphase flow using adaptive Eulerian grids. Int. J. Numer. Meth. Fluids (to appear 2003). 2. He, X.Y., Zhang, R.Y., Chen, S.Y. and Doolen, G.D.: On the three dimensional Rayleigh-Taylor instability. Phys. Fluids 11(5) (1999) 1143–1152. 3. Kim, J. and Moin, P.: Application of a fractional-step method to incompressible Navier-Stokes equations. J. Comput. Phys. 59 (1985) 308–323. 4. Lamb, H.: Hydrodynamics. Dover, New York (1932) p. 473. 5. Minev, P.D., Chen, T. and Nandakumar, K.: A finite element technique for multifluid incompressible flow using Eulerian grids. J. Comput. Phys. 187 (2003) 255–273. 6. Osher, S. and Fedkiw, R.P.: Level set methods: an overview and some recent results. J. Comput. Phys. 169 (2001) 463–502. 7. Ruprecht, D. and Heinrich, M.: A scheme for edge-based adaptive tetrahedron subdivision. Mathematical Visualization, (Ed.) Hege, H.C. and Polthier, K., Springer Verlag, Heidelberg (1998) pp. 61–70. 8. Scardovelli, R. and Zaleski, S.: Direct numerical simulation of free-surface and interfacial flow. Annu. Rev. Fluid Mech. 31 (1999) 567–603. 9. Tryggvason, G., Bunner, B., Esmaeeli, A., Juric, D., Al-Rawahi, N., Tauber, W., Han, J., Nas, S. and Jan, Y.J.: A front-tracking method for the computations of multiphase flow. J. Comput. Phys. 169 (2001) 708–759.
Schwarz-Like Methods for Approximate Solving Cooperative Systems* Ivo Marek Faculty of Civil Engineering, Czech Insititute of Technology, Prague Thákurova 7, 166 29 Praha, Czech Republic
[email protected]
Abstract. The aim of this contribution is to propose and analyze some computational means to approximate solving mathematical problems appearing in some recent studies devoted to biological and chemical networks.
Basic mathematical tools for investigating some biological and chemical networks as presented in [7,8] are recalled in Section 1. In Section 2 some variants of iterative Schwarz-like methods studied in [1,11] are described and applied to problems discussed in Section 1. An analysis and comparison of two particular Schwarz-like methods is presented in Section 4.
1
Cooperative Systems
In [7] a theory for linear problems of the type
where T is a given infinitesimal generator of a semigroup of operators is developed. Several examples mainly from biology and chemistry where the state vectors of the underlying chemical network follow an evolution (1) are presented there. In these cases the conservation of matter requires the existence of an element such that the pairing is constant during all times of the evolution so that we have
More complicated networks (and some examples are shown [8]) are described by a state vector which is formed by finitely many substates in the fashion
*
Research has been supported by grant No.201/02/0595 of the Grant Agency of the Czech Republic and grant No. MSM 210000010 of the Ministry of Education of the Czech Republic.
I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 25–38, 2004. © Springer-Verlag Berlin Heidelberg 2004
26
Ivo Marek
following an evolution
Hence, the subsystems evolve like (1) and (2) for which we developed the theory in [7]. The dependence of the operators on the data is typically on the complete state (3) rather than only on some substates. If for the states of the subsystems, the product can be formed and the “block”-diagonal operator
can be defned on X. Now (3) evolves according to
where and B is the infinitesimal generator of a semigroup of operators of class [9, p.321]. Note that structurally (6) is very similar to (1), (2). Only the infinitesimal generator itself depends on the total state (3) so that our problem becomes nonlinear. In [8] the evolution problem was assumed in the form (6) under very general conditions and an existence theorem (concerning mild solutions which in our applications become classical solutions) was proven for all times and the question of its long run behaviour settled: In fact, any solution of (6) settles in the long run at a steady state. Defining equations to determine this steady state are given there. This theorem is important not only in its own right. It also provides the basis for singular perturbation techniques on such systems to obtain analytic expressions which characterize the speed of reaction systems, and we refer to [4], [17] for the pseudo-steady state process leading to the definition of the speed of the underlying chemical networks. Note that the theory does not need the diagonal form of (5). However, it relies heavily on (2). Relation (6) is only an easy way to fit (3), (4) under the general pattern (10). The original form of the examples is (4). As in the earlier papers [7], [8] we need the theoretical basis for infinitesimal generators with monotonicity properties. The corresponding basic definitions are summarized in this section. Let be a Banach space over the field of real numbers. Let denote the dual space of Let be the corresponding complex extensions of respectively and let and be the spaces of all bounded linear operators mapping into and into respectively. In fact, we are going to provide our investigations in a Hilbert space equipped with an inner product [., .].
Schwarz-Like Methods for Approximate Solving Cooperative Systems
27
Let be a closed normal and generating cone, i.e. let (i) (ii) (iii) (iv) where denotes the norm-closure of (v) and whenever such that (vi) there exists a Property (vi) is called normality of
We let and there exist (vii) For every pair as elements of A cone satisfying condition (vii) is called a lattice cone and the partial order on a lattice order. In the terminology of H.H. Schaefer [14] is called a Banach lattice. Our theory is free of hypothesis (vii). Let and We call the dual cone of and the dual interior of respectively. If happens to be a Hilbert space then is replaced by a representation of in the sense of natural isomorphism of the dual with In the following analysis we assume that the dual interior is nonempty. A set is called if the following implication holds
A linear form
is called strictly positive, if
for all
We write in place of where and respectively. If happens to be a Hilbert space then denotes the appropriate inner product. A bounded linear operator is called if We write in this case and equivalently If T and S both in satisfy we write or equivalently If then denotes its dual and hence, In case is a Hilbetrt space, the dual operator is to be replaced by the adjoint operator defined via relations valid for all in the domain of T and in the domain of
28
Ivo Marek
Definition 1. Operator is called if there exists a vector such that for the dual map the following relation
holds. We also say that T is a transition operator of a Markov chain or process and that operator T corrersponds to vector If is a Hilbert space the dual is to be replaced by its adjoint
Definition 2. A bounded linear operator B is if for every pair of elements there is a positive integer such that This implies that in the Markov chain each state has access to every other state, i.e., the chain is ergodic [15]. The Perron-Frobenius theorem states that for irreducible, is an isolated eigenvalue, and the corresponding eigenvector is positive; see, e.g., [3]. Let and let denote its spectrum. Further, let We introduce the operator by setting where and call it complex extension of T. By definition, we let Similarly, we let where denotes the spectral radius of In order to simplify notation we will identify T and its complex extension and will thus omit the tilde sign denoting the complex extension. The set is called peripheral spectrum of T. Note that If is an isolated singularity of Laurent expansion of around
where
and
where and is such that Furthermore,
is never empty. we have the following
[16], [12]
belong to
Moreover, it holds [16]
Schwarz-Like Methods for Approximate Solving Cooperative Systems If there is a positive integer
29
such that
then is called a pole of the resolvent operator and We define the symbol
its multiplicity.
and call it the index of T at In particular, we call ind(T) the index of T instead of index of T at 0. The motivating examples are particular cases of Problem (P) defined as follows: Problem (P) To find
solutions
where B is generally an unbounded linear densely defined operator and for every is a bounded linear map on where denotes the underlying space to be specified in each particular situation. We assume that we can identify situations in which Problem (P) as formulated above possesses solutions and we are aware of conditions guaranteeing the existence of them as well as some of their properties such as uniqueness, asymptotic behaviour etc. A rather typical representative of such problem is described in our study [8]. Since our aim in the present contribution is to propose some algorithms of computational nature and analyse their properties we do not go into much details referring the reader to [8] to consulting general aspects. All properties needed for a good understanding of the numerical processes studied will be presented here.
2
Schwarz Iterative Methods
In this section we present some notations, definitions, and preliminaries. Analogous concepts on nonnegative matrices (defined here for generally infinite dimensional spaces) can be found in the standard reference [3]. By we denote the spectrum of C and by its spectral radius. By and we denote the range and null space of C, respectively. Let be a pole of the resolvent operator The multiplicity of as a pole of is called the index of C with respect to and denoted Equivalently, if it is the smallest integer for which This happens if and only if Definition 3. Let A be a densely defined being its domain of definition) and spectrally bounded from above linear operator and let be its bound, i.e., implies Assume that for there exists a system of operators such that relation
30
Ivo Marek
holds for every Operator A is called approximate if each of the operators in the collection mentioned has the form with and each being A pair of operators ( M , W) is called a splitting of A if A = M – W and exists as a bounded linear operator on A splitting of an operator A is called of type if the operator is [10]. If, in particular, both operators and W are the splitting is called regular [18]. If and are nonnegative, the splitting is called weak regular [13]. Note a weak regular splitting does require explicitely no conditions upon part W of the splitting of A. Let T be a bounded linear operator. T is called convergent if and zero-convergent, if moreover
exists
Standard stationary iterations of
the form converge if and only if either T is zero-convergent or, if T is convergent. A bounded linear operator T with unit spectral radius being an isolated pole of the resolvent operator is convergent if the following two conditions hold: (i) if and then (ii) Equivalent conditions for (ii) can be found in [3]. It is useful to write T = Q + S, where Q is the first term of the Laurent expansion of T, i.e., the eigenprojection onto the invariant subspace corresponding to see, e.g., [16]. Then QS = SQ = O, and This is called the spectral decomposition of T. The condition (i) above is equivalent to having We state a very useful Lemma; its proof can be found, e.g., in [5]. We note that when this lemma can be used to show condition (ii) above. To prove convergence one needs to show in addition that condition (i) also holds. Lemma 1. Let T be a with Then operator then
3
bounded linear operator such that If furthermore is a pole of the resolvent
Algebraic Formulation of Schwarz Methods
In this Section we want to generalize convergence of some procedures well known as algebraic Schwarz iteration techniques [1], [11]; our aim is however to analyze solving equations in infinite dimensional spaces as well. Given an initial approximation to the solution of
the (one-level) multiplicative Schwarz method can be written as the stationary iteration
Schwarz-Like Methods for Approximate Solving Cooperative Systems
31
where
and
is a certain vector in
Here
where is a suitable linear operator and its adjoint with respect to the inner product in the Hilbert space Note that each and hence each is a projection operator; i.e., Each naturally has spectral radius equal to 1. The additive Schwarz method for the solution of (13) is of the form (14), where
is a damping parameter. where The operator corresponds to the restriction operator from the whole space to a subset of the state space (usually of finite dimension the dimension of the range is infinite in general) in the domain decomposition setting, and the operator is the restriction of A to that subset. A solution using is called a local solver as in the domain decomposition method as well as in the algebraic case. We assume that our standard choice of operators follows the same idea as does the choice of the rows of as rows of the identity matrix I in case of e.g.,
Let us assume that the Hilbert space with which we provide our analyses is partially ordered by a closed normal cone generating i.e. Moreover, let subsets exist such that
is and holds if and only if there exists an element such that In order to allow overlaps of individual reduction maps we do not assume that and Obviously, if and only if there are and such that and if and only if whenever and Formally, space can be considered as a direct sum
32
Ivo Marek
where is the “complementary” subspace to decomposition of operator A given by formula
where maps into We assume that the maps
and
We also have a corresponding
maps
into
are diagonal operators, i.e. for some real In fact, we expect that similarly as in the finite dimensional case operators will signal whether the method chosen does possess some overlaps and how extensive they are. It is easy to see that as in case of finite dimensional situation both and are [3]. For each we construct diagonal operators associated with chosen
If A is an collection of operators
for each associated with
we construct a second as follows
where is invertible diagonal operator representing a “diagonal” of A. The following result comes from [1]. Proposition 1. Let A be a nonsingular Let be defined as in (20). Then the splittings are regular (and thus weak regular and of nonnegative type). In the cases considered in this paper, we always have that defined in (20) are nonsingular. With the definitions (19) and (20) we obtain the following equality We can thus rewrite (15) as
Similarly, (17) can be rewritten as
Schwarz-Like Methods for Approximate Solving Cooperative Systems
33
This is how we interpret the multiplicative and additive Schwarz iterations. In [1] it was shown that when A is nonsingular, and thus, the method (12) is convergent. Furthermore, there exists a unique splitting A = M – W such that This splitting is a weak regular splitting. In this paper we want to explore the convergence of (12), using the iterations defined by (23), (24), when A is singular.
4
Two Approaches to Approximate Solving Stationary Equation
We are going to describe two ways for constructing solutions to stationary equations. The first one is based on a application of one of Schwarz algorithms directly to the stationary equation, the second one utilizes the asymptotic behaviour of solutions of the appropriate evolution. The second alternative is suitable in particular for problems when no additional information is available such as irreducibility etc. As classical properties of M-matrices suggest strict positive diagonals may strongly influence convergence and the speed of convergence of the investigated iterative proccesses. We recall a useful Lemma 2. Let Then
satisfy is convergent.
and
with some real
Proof. Obviously, and hence, For completing the proof we need to show that 1 is a unique spectral point with modulus Let By hypothesis, and can be written as Hence, Let with reals and It follows that
only if or, equivalently, if is real and hence positive. This completes the proof of the Lemma. In [8] it has been shown that a solution to Problem (P) gets stationary and is a solution to
where and are suitable nonnegative reals and Since, by hypothesis,
the initial condition in (10).
34
Ivo Marek
where and denote the appropriate discretizations of C and spectively, it is an easy matter to show that
re-
satisfies Thus, in view of Definition 3,
is
corresponding to vector
Theorem 1. Let be a Hilbert space with an inner product [.,.]. Let A = I –B, where is a operator such that with Let be a positive integer and be splittings of nonnegative type such that the diagonals of are positive. Then
and are convergent operators. Furthermore, there is a splitting of nonnegative type such that erties:
and the iteration operator T possesses the following prop-
and The existence of a splitting of nonnegative type, and properties (28) and (29) also hold for Proof. We begin with the operator Let be such that i.e., For each splittings of we then have that This implies that and by Lemma 1 we have that and that the index is 1. To show that is convergent, we show that for some real This follows from the fact that each of the operators satisfies relation with positive reals We follow a similar logic for the multiplicative Schwarz iteration operator (23). Since and thus and Each factor in (23) can be written as
and since and each factor is nonnegative. For a row in which is zero, the diagonal entry in this factor has value one. For a row in which has value one, the diagonal entry in this factor is the positive diagonal entry of Thus, again, we have a finite product of operators, each dominanting a positive multiple of the identity operator, implying
Schwarz-Like Methods for Approximate Solving Cooperative Systems
35
that the product T does dominate a positive multiple of the identity operator too, and therefore it is convergent. The rest of the proof applies equally to T and we only detail it for T. The matrix T being convergent implies the spectral decomposition (28), where Q is the spectral projection onto the eigenspace of T corresponding to Furthermore since We show now that According to construction of T, the null spaces satisfy Any element of which does not belong to has to have a form for some and Since we have that On the other hand a contradiction. Since we then have that the existence of a splitting of the form (27) follows similarly as does the finite dimensional analog of Theorem 1 from Theorem 2.1 of [2]. The fact that indicates that this splitting is of nonnegative type. With this splitting, using (28) the following identity holds AQ = M(I – T)Q = O, so we also have (29). An example of splittings that lead to iteration matrices satisfying the hypotheses of Theorem 1 is described in the following proposition requiring no proof. It provides a possible modification to the local solvers, when the iteration operator defined by (20) does not dominate a positive multiple of the identity operator. Proposition 2. Let numbers. Let
Let
be any positive real be defined by
and where are defined in (20)-(21). Then, the splittings are regular, and iteration operator dominate a positive multiple of the identity operator. Let us recall that we want to compute the stationary state, i.e. a solution of the system (25) This problem can be reformulated in terms of a new iterative process with the generating nonnegative operators C and
An alternative to the method of approximate solving stationary equation of Problem (P) as described in Theorem 1 is to compute the limit using process (31). From a variety of possible choices of rational approximations of the exponential we choose one from the class of limited Padé approximations, say
36
Ivo Marek
with appropriate real
and polynomial
of degree
Denoting
we want to compute according to (31)
The above process can be implemented as follows. Let us omit the discretization parameter index and set and
Then
Convergence of the method just described is an easy consequence of the fact that the operators are nonsingular in the spirit of Definition 3 and the convergence results of [1]. Actually, we have Theorem 2. Let be a Hilbert space over the reals generated by a closed normal cone Assume B is a generally unbounded linear operator defined on a dense domain and its adjoint satisfies relation We assume further that B generates a semigroup of operators of class such that Finally assume that for any operator is an satisfying Then the iteration process (32) returns a sequence of approximations to a unique solution to Problem (P) such that
5
Conclusions
Nowadays it is accepted by the community of numerical analysts that two- and generally multi-level iterative methods offer an essentially broader variety of tools to solve large scale computational problems. In this context Schwarz and Schwarz-like methods play a quite important role. Many contributions of many authors document this statement as a rule by investigating problems characterized by nonsingular operators. An emphasis of our approach is just the opposite that is to problems with singular operators. Another goal of our analyses is that we consider the computational problems in their original form, i.e. we work with
Schwarz-Like Methods for Approximate Solving Cooperative Systems
37
generally infinite dimensional objects and let discretizations to be made at an appropriate moment, e.g. at each iteration step. We apply our Schwarz-like methods to a problem coming from stochastic modeling in biology and chemistry. We can thus profit from having nicely structured operators but suffer of approaching problems with hardly accessible data. We thus propose two methods each suitable in the corresponding situation. The first method assumes all data accessible and the second just the opposite. In particular, the method using auxilliary time evolution does require no apriori knowledge of location as well as access to each single data. As example let us mention irreducibility of the operators of the model and access to matrix elements of appropriate discretizations. The latter is compensated by ability of our method of an easy computation of corresponding matrix actions.
References l. Benzi M., Frommer A., Nabben R., Szyld D. Algebraic theory of multiplicative Schwarz methods. Numer. Math. 89, 605-639 (2002). 2. Benzi M., Szyld D. B. Existence and uniqueness of splittings for stationary iterative methods with applications to alterning methods. Numer. Math. 76, 309-321 (1997). 3. Berman A., Plemmons R. Non-negative Matrices in the Mathematical Sciences. Academic Press, 1979. 4. Bohl E., Boos W. Quantitative analysis of binding protein-mediated ABC transport system, J. Theor. Biology 186, 65-74 (1997). 5. Bohl E., Marek I. A model of amplification, J. Comput. Appl. Math. 63 , 27-47, 1995. 6. Bohl E., Marek I. A nonlinear model involving M - operators. An amplification effect measured in the cascade of vision. J. Comput. Appl. Math. 60, 13-28, (1994). 7. Bohl E., Marek I. A stability theorem for a class of linear evolution problems, Integral Equations Operator Theory. 34, 251-269, (1999). 8. Bohl E., Marek I. Existence and uniqueness results for nonlinear cooperative systems. Operator Theory : Advances and Applications, Vol. 130, 153-170 (2001). 9. Hille E., Phillips R.S. Functional Analysis and Semigroups. Amer. Math. Socitey Coll. Publ. Vol XXXI, Third printing of Revised Edition Providence, Rhode Island, 1968. 10. Marek I. Frobenius theory of positive operators. Comparison theorems and applications. SIAM Journal on Applied Mathematics 19, 608–628, (1970). 11. Marek I., Szyld D. Algebraic Schwarz methods for the numerical solution of Markov chains. Linear Algebra Appl. Submitted 2003. 12. Marek I., Žitný K. Analytic Theory of Matrices for Applied Sciences, Vol 1., Teubner Texte zur Mathematik Band 60, Leipzig, 1983. 13. J. M. Ortega and W. Rheinboldt. Iterative Solution of Nonlinear Equations In Several Variables. Academic Press, New York, San Francisco, London, 1970. 14. Schaefer H.H. Banach Lattices and Positive Operators. Springer-Verlag BerlinHeidelberg-New York, 1974. 15. Stewart W.J. Introduction to the Numerical Solution of Markov Chains. Princeton University Press. Princeton NJ, 1994. 16. Taylor A. E., Lay D.C. Introduction to Functional Analysis. Second edition, J. Wiley Publ. New York, 1980.
38
Ivo Marek
17. Tralau C., Greller G., Pajatsch M., Boos W., Bohl E. Mathematical treatment of transport data of bacterial transport system to estimate limitation in diffusion through the outer membrane, J. Theor. Biol. 207, 1-14, (2000). 18. R. S. Varga. Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, New Jersey, 1962. Second Edition, revised and expanded, Springer, Berlin, Heidelberg, New York, 2000.
Computational Infrastructure for Parallel, Distributed, and Grid-Based Monte Carlo Computations Michael Mascagni1 and Yaohang Li2 1
Department of Computer Science and School of Computational Science and Information Technology, Florida State University, Tallahassee, FL 32306-4530, USA
[email protected] http://www.cs.fsu.edu/~mascagni 2
North Carolina A&T State University, Greensboro, NC 27411, USA
[email protected]
Abstract. Monte Carlo applications are widely perceived as computationally intensive but naturally parallel. Therefore, they can be effectively executed using the dynamic bag-of-work model which is well suited to parallel, distributed, and grid-based architectures. This paper concentrates on providing computational infrastructure for Monte Carlo applications on such architectures. This is accomplished by analyzing the characteristics of large-scale Monte Carlo computations, and leveraging the existing Scalable Parallel Random Number Generators (SPRNG) library. Based on these analyses, we improve the efficiency of subtaskscheduling by implementing and analyzing the “N-out-of-M” strategy, and develop a Monte Carlo-specific lightweight checkpointing technique, which leads to a performance improvement. Also, we enhance the trustworthiness of Monte Carlo applications on these architectures by utilizing the statistical nature of Monte Carlo and by cryptographically validating intermediate results utilizing the random number generator already in use in the Monte Carlo application. All these techniques lead to a highperformance grid-computing infrastructure that is capable of providing trustworthy Monte Carlo computation services.
1 Introduction Readers are most likely already familiar with parallel and distributed computing architectures, so we choose not to elaborate on them further. Thus, grid computing is characterized by the large-scale sharing and cooperation of dynamically distributed resources, such as CPU cycles, communication bandwidth, and data, to constitute a computational environment [1]. In the grid’s dynamic environment, from the application point-of-view, two issues are of prime importance: performance – how quickly the grid-computing system can complete the submitted tasks, and trustworthiness – that the results obtained are, in fact, due to the computation requested. To meet these two requirements, many grid-computing or distributed-computing systems, such as Condor [2], HARNESS [3], Javelin [4], I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 39–52, 2004. © Springer-Verlag Berlin Heidelberg 2004
40
Michael Mascagni and Yaohang Li
Globus [5], and Entropia [7], concentrate on developing high-performance and trust-computing facilities through system-level approaches. In this paper, we are going to analyze the characteristics of Monte Carlo applications, which are a potentially large computational category of parallel, distributed, and grid applications, to develop approaches to address performance and trustworthiness issues at the application level. The remainder of this paper is organized as follows. In §2, we analyze the characteristics of Monte Carlo applications. We also quickly describe the random number generation requirements for these applications on parallel, distributed, and grid-based architectures. We then develop a generic grid-computing paradigm for Monte Carlo computations. We discuss how to take advantage of the characteristics of Monte Carlo applications to improve the performance and trustworthiness of Monte Carlo grid computing in §3 and §4, respectively. Finally, §5 summarizes our conclusions and future research directions.
2
Grid-Based Monte Carlo Applications
Among parallel, distributed, and grid applications, those using Monte Carlo methods, which are widely used in scientific computing and simulation, have been considered too simplistic for consideration due to their natural parallelism. However, below we will show that many aspects of Monte Carlo applications can be exploited to provide much higher levels of performance and trustworthiness for computations on these architectures. According to word of mouth, about 50% of the CPU time used on supercomputers at the U. S. Department of Energy National Labs is spent on Monte Carlo computations. Unlike data-intensive applications, Monte Carlo applications are usually computation intensive [6], and they tend to work on relatively small data sets. Parallelism is a way to accelerate the convergence of a Monte Carlo computation. If N processors execute N independent copies of a Monte Carlo computation, the accumulated result will have a variance N time smaller than that of a single copy. In a distributed Monte Carlo application, once a distributed task starts, it can usually be executed independently with almost no interprocess communication. Therefore, Monte Carlo applications are perceived as naturally parallel, and they can usually be programmed via the so-called dynamic bag-of-work model. Here a large task is split into smaller independent subtasks and each are then executed separately. Effectively using the dynamic bag-of-work model for Monte Carlo requires that the underlying random number streams in each subtask be independent in a statistical sense. The SPRNG (Scalable Parallel Random Number Generators) library [11] was designed to use parameterized pseudorandom number generators to provide independent random number streams to parallel processes. Some generators in SPRNG can generate up to independent random number streams with sufficiently long period and good quality [13]. These generators meet the random number requirements of most Monte Carlo applications for these types of architectures.
Computational Infrastructure
41
SPRNG was originally designed to provide independent and dynamic streams of random numbers for massively parallel supercomputers. The design of SPRNG was based on the needs of Monte Carlo applications, like neutronics. In neutronics, it is commonplace to associate a single random number stream with each neutron. When a neutron splits into more neutrons, each child neutron is then associated with a new (and hopefully independent) random number stream. Given such a computation, SPRNG ensures that, when desired, such a computation performed on a parallel or distributed machine can be entirely reproducible. The details of how this is achieved is beyond the current scope [11]. However, these capabilities of SPRNG are extensible to distributed and grid-based architectures, and form the underpinnings for the grid services we will discuss. In the remainder of this paper we thus focus exclusively on grid computing issues for Monte Carlo applications. The intrinsically parallel aspect of Monte Carlo applications makes them an ideal fit for the grid-computing paradigm. In general, grid-based Monte Carlo applications can divide the Monte Carlo task into a number of subtasks by the task-split service and utilize the grid’s schedule service to dispatch these independent subtasks to different nodes [15]. The connectivity services provide communication facilities among nodes providing computational services. The execution of a subtask takes advantage of the storage service of the grid to store intermediate results and to store each subtask’s final (partial) result. When the subtasks are done, the collection service can be used to gather the results and generate the final result of the entire computation. The inherent characteristics of Monte Carlo applications motivate the use of grid computing to effectively perform large-scale Monte Carlo computations. Furthermore, within this Monte Carlo grid-computing paradigm, we can use the statistical nature of Monte Carlo computations and the cryptographic aspects of random numbers to reduce the wallclock time and to enforce the trustworthiness of the computation.
3 3.1
Improving the Performance of Grid-Based Monte Carlo Computing The N-out-of-M Strategy
Subtask-Scheduling Using the N-out-of-M Strategy. The nodes that provide CPU cycles in a grid system will most likely have computational capabilities that vary greatly. A node might be a high-end supercomputer, or a low-end personal computer, even just an intelligent widget. In addition, these nodes are geographically widely distributed and not centrally manageable. A node may go down or become inaccessible without notice while it is working on its task. Therefore, a slow node might become the bottleneck of the whole computation if the assembly of the final result must wait for the partial result generated on this slow node. A delayed subtask might delay the accomplishment of the whole task while a halted subtask might prevent the whole task from ever finishing. To address this problem, system-level methods are used in many grid systems. For
42
Michael Mascagni and Yaohang Li
example, Entropia [7] tracks the execution of each subtask to make sure none of the subtasks are halted or delayed. However, the statistical nature of Monte Carlo applications provides a shortcut to solve this problem at the application level. Suppose we are going to execute a Monte Carlo computation on a grid system. We split it into N subtasks, with each subtask based on its unique independent random number stream. We then schedule each subtask onto the nodes in the grid system. In this case, the assembly of the final result requires all the N partial results generated from the N subtasks. Each subtask is a “key” subtask, since the suspension or delay of any one of these subtasks will have a direct effect on the completion time of the whole task. When we are running Monte Carlo applications, what we really care about is how many random samples (random trajectories) we must obtain to achieve a certain, predetermined, accuracy. We do not much care which random sample set is estimated, provided that all the random samples are independent in a statistical sense. The statistical nature of Monte Carlo applications allows us to enlarge the actual size of the computation by increasing the number of subtasks from N to M, where M > N. Each of these M subtasks uses its unique independent random number set, and we submit M instead of N subtasks to the grid system. Therefore, M bags of computation will be carried out and M partial results may be eventually generated. However, it is not necessary to wait for all M subtasks to finish. When N partial results are ready, we consider the whole task for the grid system to be completed. The application then collects the N partial results and produces the final result. At this point, the grid-computing system may broadcast abort signals to the nodes that are still computing the remaining subtasks. We call this scheduling strategy the N-out-of-M strategy. In the N-out-of-M strategy more subtasks than are needed are actually scheduled, therefore, none of these subtasks will become a “key” subtask and we can tolerate at most M – N delayed or halted subtasks. Also notice that the Monte Carlo computation using the N-out-of-M strategy is reproducible, because we know exactly which N out of M subtasks are actually involved and which random numbers were used. Thus each of these N subtasks can be reproduced later. However, if we want to reproduce all of these N subtasks at a later time on the grid system, the N-out-of-N strategy must be used. One drawback of the N-out-of-M strategy is we must execute more subtasks than actually needed and will therefore increase the computational workload on the grid system. However, our experience with distributed computing systems such as Condor and Javelin shows that most of the time there are more nodes providing computing services available in the grid system than subtasks. Therefore, properly increasing the computational workload to achieve a shorter completion time for a computational task should be an acceptable tradeoff in a grid system. Analysis of the N-out-of-M Strategy. In Monte Carlo applications, N is determined by the application and depends on the number of random samples
Computational Infrastructure
43
or random trajectories needed to obtain a predetermined accuracy. The problem is thus how to choose the value M properly. A good choice of M can prevent a few subtasks from delaying or even halting the whole computation. However, if M is chosen too large, there may be little benefit to the computation at the cost of significantly increasing the workload of the grid system. In order to determine a proper value of M to achieve a specific performance requirement, we study the grid behavior and consider some system parameters. In the Nout-of-M strategy, the completion time of a Monte Carlo computational task depends on the performance of each individual node that is assigned a subtask, the node failure rate, and also the interconnection network failure rate. We make the following assumptions to set up our model:
1. The execution of a task completely occupies a node on the grid, and no other jobs can be executed on the same node concurrently. 2. Compared to the execution time, the tasks’ scheduling time and result collection time is short enough to be ignored. 3. Each node works on its task independently. 4. Each node has an equal probability of obtaining a task from the schedule service. The tasks are scheduled without noticing the performance of each node. To analyze this we establish a Petri Net (PN) model of the N-out-of-M strategy. This PN model has M nodes in total. A node, alternates between an up state (place and a down state (place Transition represents node unavailability (with unavailability rate and transition node back to service (with availability rate Transition is assigned the task progress threshold W (usually 100%) so that the subtask completion condition (token in is reached when W is hit. When gathers N tokens, transition enables firing and a token in indicates the completion of the Monte Carlo task. We also establish a simpler binomial model for the subtask-scheduling scheme using the N-out-of-M strategy based on the above PN model. Assume that the probability of a subtask completing by time is given by The function describes the aggregate probability over the pool of nodes in the grid. In a reallife grid system, could be measured by computing the empirical frequencies of completion times over the pool. In this paper, we model based on an analytic probability distribution function. Let S be the total number of nodes available in the grid system, be the probability of node participating in the computations is up, where be the service rate of node which can be measured as the number of tasks that can be finished within a specific period of time without interruption. Considering node availability, the actual service rate, in node is At time the probability that a Monte Carlo subtask will be done on node is Since each node has equal probability to be scheduled a subtask, can be represented as
44
Michael Mascagni and Yaohang Li
If the service rates, density function
conform to a distribution with probability can thus be written as
Here L is the maximum value of in the computation. Typically, if all of the nodes have the same service rate fied to
can be simpli-
Then, the probability that exactly N out of M subtasks are complete at time is given by
We can approximate Then,
using a Poisson distribution with can be approximated as
The probability that at least N subtasks are complete is thus given by
The old strategy can be thought of as “N-out-of-N” which has probability given by
Now the question is to decide on a reasonable value for M to satisfy a required task completion probability (when N subtasks are complete on the grid). Unfortunately, it is hard to explicitly represent M in analytic form. However, we use a numerical method, which gradually increases M by 1 to evaluate until the value of is greater than This empirically gives us the minimum value of M. An alternative approach to estimate M/N is to use a normal distribution to approximate the underlying binomial. When and the binomial distribution can be approximated by a normal curve with mean and standard deviation Then, we can find the minimum value M that satisfies
Computational Infrastructure
45
Fig. 1. Simulations and Model Prediction of the N-out-of-M Scheduling Strategy for Grid Monte Carlo Applications.
where is the normal cumulative distribution function. In a grid system, nodes providing computational services join and leave dynamically. Some nodes are considered to be “transient” nodes, which provide computational services temporarily and may depart from the system permanently. A subtask submitted to a “transient” node may have no chance of being finished. Suppose the fraction of “transient” nodes in a grid is then, we need to enlarge M to to tolerate these never-finished subtasks. Simulation of the N-out-of-M Strategy. In our simulation program of the N-out-of-M strategy, we simulated a 1,000-node computational grid. Nodes join and leave the system with a specified probability. Also, nodes have a variety of computational capabilities. Each simulation is run for 1,000 time steps. (A task running on a node with service rate will take time steps, e.g., a fast node with service rate 0.01 will take 100 time steps to complete the task while a slow one with service rate 0.001 will take 1.000) At each time step, a certain number of nodes go down while a certain number of nodes become available for computation. We built our simulations in order to
1. evaluate the validity of our model, and to 2. compare the performance of the N-out-of-M strategy in grid systems with different configurations. Figure 1 shows our simulation results and model prediction of the N-out-of-M strategy for grid Monte Carlo applications. Our analytical model matches the simulation results quite well. Also, we can find that with the proper choice of M (20 in the graph), the Monte Carlo task completion time can be improved
46
Michael Mascagni and Yaohang Li
Fig. 2. Simulations of the N-out-of-M Strategy on a Grid System with Nodes Service Rates Normally Distributed (Mean=0.005, Variance=0.001).
significantly over the N-out-of-N strategy. However, if we enlarge M too much, the workload of the system increases without significantly reducing the Monte Carlo task completion time. Also, we notice that as time goes on, the N-out-ofM strategy always has a higher probability of completion than the N-out-of-N strategy, although they all converge to probability one at large times. Figures 2 and 3 show the simulation results of the N-out-of-M strategy in different grid systems. Both simulated grid systems assume that the service rates of nodes are normally distributed with the same means (0.005) but different variances (0.001 in Figure 2 and 0.003 in Figure 3). Figure 2 simulates a grid comprised of nodes with similar performance characteristics. This can be a grid constructed from computers in a computer lab that have similar performance parameters. On the other hand, Figure 3 is the simulation of a grid whose nodes have computational capabilities in a wide range. In practice, this grid can be a system with geographically widely distributed nodes like SETI@home [9], where a node might be a high-end supercomputer, or a low-end personal computer. From the graphs, we see that the N-out-of-M scheduling strategy improves the Monte Carlo task completion time in both grid systems; however, we gain more significant improvement in the system comprised of nodes with service rates having a large variance. This experimental result indicates that the N-out-of-M strategy is more effective in a grid system where an individual node’s performance varies greatly. More interestingly, the simulation results also show that, in both grid systems, with a sufficiently large value of M, the time values after which the Monte Carlo task is complete with a high probability is close to 200 time steps, which is exactly the subtask completion time for a single node with the mean (0.005) service rate. Therefore, we can expect that, with a proper number of sub-
Computational Infrastructure
47
Fig. 3. Simulations of the N-out-of-M Strategy on a Grid System with Nodes Service Rates Normally Distributed (Mean=0.005, Variance=0.003).
tasks scheduled using the N-out-of-M strategy, the Monte Carlo task completion time on a grid can be made to be almost the same as the subtask completion time in a node with average computational capability. Lightweight Checkpointing. A subtask running on a node of a grid system may take a very long time to finish. The N-out-of-M strategy is an attempt to mitigate the effect of this on the overall running time. However, if checkpointing is incorporated, one can directly attack reducing the completion time of the subtasks. Some grid computing systems implement a process-level checkpoint. Condor, for example, takes a snapshot of the process’s current state, including stack and data segments, shared library code, process address space, all CPU states, states of all open files, all signal handlers, and pending signals [12]. On recovery, the process reads the checkpoint file and then restores its state. Since the process state contains a large amount of data, processing such a checkpoint is quite costly. Also, process-level checkpointing is very platform-dependent, which limits the possibility of migrating the process-level checkpoint to another node in a heterogeneous grid-computing environment. Fortunately, Monte Carlo applications have a structure highly amenable to application-based checkpointing. Typically, a Monte Carlo application starts in an initial configuration, evaluates a random sample or a random trajectory, estimates a result, accumulates means and variances with previous results, and repeats this process until some termination condition is met. Although different Monte Carlo applications may have very different implementations, many of them can be developed or adjusted in a typical programming structure that consists of initialization, followed by a loop for generating statistical samples, and ending with the summation of the overall statistics.
48
Michael Mascagni and Yaohang Li
Thus, to recover an interrupted computation, a Monte Carlo application needs to save only a relatively small amount of information. The necessary information to reconstruct a Monte Carlo computation image at checkpoint time will be the current results based on the estimates obtained so far, the current status and parameters of the random number generators, and other relevant program information like the current iteration number. This allows one to make a smart and quick application checkpoint in most Monte Carlo applications. Using XML [8] to record the checkpointing information, we can make this checkpoint platform-independent. More importantly, compared to a process checkpoint, the application-level checkpoint is much smaller in size and much quicker to generate. Therefore, it should be relatively easy to migrate a Monte Carlo computation from one node to another in a grid system. With the application-level checkpointing and recovery facilities, the typical Monte Carlo application’s programming structure can be amended as described above. However, the implementation of application level checkpointing will somewhat increase the complexity of developing new Monte Carlo grid applications.
4 4.1
Enhancing the Trustworthiness of Grid-Based Monte Carlo Computing Distributed Monte Carlo Partial Result Validation
The correctness and accuracy of grid-based computations are vitally important to an application. In a grid-computing environment, the service providers of the grid are often geographically separated with no central management. Faults may hurt the integrity of a computation. These might include faults arising from the network, system software or node hardware. A node providing CPU cycles might not be trustworthy. A user might provide a system to the grid without the intent of faithfully executing the applications obtained. Experience with SETIhome has shown that users often fake computations and return wrong or inaccurate results. The resources in a grid system are so widely distributed that it appears difficult for a grid-computing system to completely prevent all “bad” nodes from participating in a grid computation. Unfortunately, Monte Carlo applications are very sensitive to each partial result generated from each subtask. An erroneous partial result will most likely lead to the corruption of the whole grid computation and thus render it useless. To enforce the correctness of the computation, many distributed computing or grid systems adapt fault-tolerant methods, like duplicate checking [10] and majority vote [16]. In these approaches, subtasks are duplicated and carried out on different nodes. Erroneous partial results can be found by comparing the partial results of the same subtask executed on different nodes. Duplicated checking requires doubling computations to discover an erroneous partial result. Majority vote requires at least three times more computation to identify an erroneous partial result. Using duplicate checking or majority vote will significantly increase the workload of a grid system.
Computational Infrastructure
49
In the dynamic bag-of-work model as applied to Monte Carlo applications, each subtask works on the same description of the problem but estimates based on different random samples. Since the mean in a Monte Carlo computation is accumulated from many samples, its distribution will be approximately normal based in the Central Limit Theorem. Suppose are the partial results generated from individual nodes on a grid system. The mean of these partial results is
and we can estimate its standard error,
via the following formula
Specifically, the Central Limit Theorem states that should be distributed approximately as a random variable with mean standard deviation and degrees-of-freedom. However, since the number of subtasks, is often large, we may instead approximate the distribution with the normal. Standard normal confidence interval theory states that with 68% confidence that the exact mean is within 1 standard deviation of with 95% confidence within 2 standard deviations, and 99% confidence within 3 standard deviations. This statistical property of Monte Carlo computation can be used to develop an approach for validating the partial results of a large grid-based Monte Carlo computation. Here is the proposed method for distributed Monte Carlo partial result validation. Suppose we are running Monte Carlo subtasks on the grid, and the subtask returns partial result, We anticipate that the are approximately normally distributed with mean, and standard deviation, We expect that about one of the in this group of to lie outside a normal confidence interval with confidence In order to choose a confidence level that permits events we expect to see, statistically, yet flags events as outliers requires us to choose a multiplier, so that we flag events that should only occur once in a group of size The choice of is rather subjective, but implies that in only 1 in 10 runs of size we should expect to find an outlier with confidence With a given choice of one computes the symmetric normal confidence interval based on a confidence of Thus the confidence interval is where is unit normal value such that If
is in this confidence interval, we can consider this
partial result as trustworthy. However, if falls out of the interval, which may happen merely by chance with a very small probability, this particular partial result is suspected. There are two possibilities for a partial result, to fall out of the confidence interval. These are
50
Michael Mascagni and Yaohang Li
1. errors occur during the computation of this subtask, or 2. a rare event with very low probability is captured.
In former case, this partial result is erroneous and should be discarded, whereas in the latter case, we need to take it into consideration. To identify these two cases, we can rerun the particular subtask that generated the suspicious partial result on a trusted node for further validation. This Monte Carlo partial result validation method supplies us with a way to identify suspicious results without running more subtasks. This method assumes that the majority of the nodes in grid system are “good” service providers, which can correctly and faithfully execute their assigned task and transfer the result. If most of the nodes are malicious, this validation method may not be effective. However, experience has shown that the fraction of “bad” nodes in volunteered computation is very small.
4.2
Intermediate Value Checking
Usually, a grid-computing system compensates the service providers to encourage computer owners to supply resources. Many Internet-wide grid-computing projects, such asSETI@home [9], have the experience that some service providers don’t faithfully execute their assigned subtasks. Instead they attempt to provide bogus partial results at a much lower personal computational cost in order to obtain more benefits. Checking whether the assigned subtask from a service provider is faithfully carried out and accurately executed is a critical issue that must be addressed by a grid-computing system. One approach to check the validity of a subtask computation is to validate intermediate values within the computation. Intermediate values are quantities generated within the execution of the subtask. To the node that runs the subtask, these values will be unknown until the subtask is actually executed and reaches a specific point within the program. On the other hand, to the clever application owner, certain intermediate values are either pre-known and secret or are very easy to generate. Therefore, by comparing the intermediate values and the pre-known values, we can control whether the subtask is actually faithfully carried out or not. Monte Carlo applications consume pseudorandom numbers, which are generated deterministically from a pseudorandom number generator. If this pseudorandom number generator has a cheap algorithm for computing arbitrarily within the period, the random numbers are perfect candidates to be these cleverly chosen intermediate values. Thus, we have a very simple strategy to validate a result from subtasks by tracing certain predetermined random numbers in Monte Carlo applications. For example, in a grid Monte Carlo application, we might force each subtask to save the value of the current pseudorandom number after every N (e.g., N = 100,000) pseudorandom numbers are generated. Therefore, we can keep a record of the Nth, 2Nth, ..., random numbers used in the subtask. To validate the actual execution of a subtask on the server side, we can just recompute the Nth, 2Nth, . . . , random numbers applying the specific generator with
Computational Infrastructure
51
the same seed and parameters as used in this subtask. We then simply match them. A mismatch indicates problems during the execution of the task. Also, we can use intermediate values of the computation along with random numbers to create a cryptographic digest of the computation in order to make it even harder to fake a computational result. Given our list of random numbers, or a deterministic way to produce such a list, when those random numbers are computed, we can save some piece of program data current at that time into an array. At the same time we can use that random number to encrypt the saved data and incorporate these encrypted values in a cryptographic digest of the entire computation. At the end of the computation the digest and the saved values are then both returned to the server. The server, through cryptographic exchange, can recover the list of encrypted program data and quickly compute the random numbers used to encrypt them. Thus, the server can decrypt the list and compare it to the “plaintext” versions of the same transmitted from the application. Any discrepancies would flag either an erroneous or faked result. While this technique is certainly not a perfect way to ensure correctness and trustworthiness, a user determined on faking results would have to scrupulously analyze the code to determine the technique being used, and would have to know enough about the mathematics of the random number generator to leap ahead as required. In our estimation, surmounting these difficulties would far surpass the amount of work saved by gaining the ability to pass off faked results as genuine.
5
Conclusions
Monte Carlo applications generically exhibit naturally parallel and computationally intensive characteristics. Moreover, we can easily fit the dynamic bag-of-work model, which works so well for Monte Carlo applications, onto a grid system to implement large-scale grid-based Monte Carlo computing. Furthermore, based on the analysis of grid-based Monte Carlo applications, we may take advantage of the statistical nature of Monte Carlo calculations and the cryptographic nature of random numbers to enhance the performance and trustworthiness of this Monte Carlo grid-computing infrastructure at the application level. We are developing a Grid-Computing Infrastructure for Monte Carlo Applications (GCIMCA) based on the Globus toolkit [5] and the SPRNG library [11], using the techniques described in this paper. The infrastructure software aims to provide grid services to facilitate the development of grid-based Monte Carlo applications and the execution of large-scale Monte Carlo computations in a grid-computing environment. At the same time, we are also trying to execute some real-life large-scale Monte Carlo applications, such as the Monte Carlo simulation of Ligand-Receptor interaction in structured protein systems [17] and the Monte Carlo molecular modeling applications, on our developing grid-computing infrastructure.
52
Michael Mascagni and Yaohang Li
References 1. I. Foster, C. Kesselman, and S. Tueske, The Anatomy of the Grid, International Journal of Supercomputer Applications 15 3 (2001) 1–25. 2. M. Litzkow, M. Livny, and M. Mutka, Condor–A Hunter of Idle Workstations, Proceedings of the 8th International Conference of Distributed Computing Systems, (1998) 104–111. 3. M. Beck, J. Dongarra, G. Fagg, A. Geist, P. Gray, J. Kohl, M. Migliardi, K. Moore, T. Moore, P. Papadopoulous, S. Scott, and V. Sunderam, HARNESS: A Next Generation Distributed Virtual Machine, Journal of Future Generation Computer Systems, 15 5/6 (1999) 571–582. 4. B. O.Christiansen, P. Cappello, M. F. Ionescu, M. O. Neary, K. E. Schauser, and D. Wu, Javelin: Internet-Based Parallel Computing Using Java, Concurrency: Practice and Experience, 9 11 (1997) 1139–1160. 5. I. Foster and C. Kesselman, Globus: A Mmetacomputing Infrastructure Toolkit, International Journal of Supercomputer Applications, 11 2 (1997) 115–128. 6. A. Srinivasan, D. M. Ceperley, and M. Mascagni, Random Number Generators for Parallel Applications, Monte Carlo Methods in Chemical Physics, 105 (1997) 13–36. 7. Entropia website: http://www.entropia.com. 8. XML website: http://www.xml.org. 9. E. Korpela, D. Werthimer, D. Anderson, J. Cobb, and M. Lebofsky, SETI@homeMassively Distributed Computing for SETI, Computing in Science and Engineering, 3 1 (2001) 78–83. 10. C. Aktouf, O. Benkahla, C. Robach, and A. Guran, Basic Concepts & Advances in Fault-Tolerant Computing Design, World Scientific Publishing Company, 1998. 11. M. Mascagni and A. Srinivasan, Algorithm 806: SPRNG: A Scalable Library for Pseudorandom Number Generation, ACM Transactions on Mathematical Software, 26 (2000) 436–461. 12. M. Livny, J. Basney, R. Raman, and T. Tannenbaum, Mechanisms for High Throughput Computing, SPEEDUP Journal, 11 1 (1997) 13. SPRNG website: http://sprng.cs.fsu.edu. 14. Condor website: http://www.cs.wisc.edu/condor. 15. R. Buyya, S. Chapin, and D. DiNucci, Architectural Models for Resource Management in the Grid, In: R. Buyya, M. Baker (Eds.): Grid Computing — GRID 2000, Lecture Notes in Computer Science, 1971, Springer Verlag (2000) 18–35. 16. L. F. G. Sarmenta, Sabotage-Tolerance Mechanisms for Volunteer Computing Systems, Proceedings of ACM/IEEE International Symposium on Cluster Computing and the Grid (CCGrid’01), (2001) 561–572. 17. Y. Li, M. Mascagni, and M. H. Peters, Grid-based Nonequilibrium Multiple-Time Scale Molecular Dynamics/Brownian Dynamics Simulations of Ligand-Receptor Interactions in Structured Protein Systems, Proceedings of the First BioGrid Workshop at the 3rd IEEE/ACM Symposium Cluster Computing and the Grid, (2003) 568–573.
Parallel Solution of Very Large Sparse Systems of Linear Algebraic Equations Zahari Zlatev National Environmental Research Institute Frederiksborgvej 399, P. O. Box 358, DK-4000 Roskilde, Denmark
[email protected] http://www.dmu.dk/AtmosphericEnvironment/staff/zlatev.htm
Abstract. Systems of linear algebraic equations occur very often when large-scale mathematical models are treated. The solution of these systems is as a rule the most time-consuming part of the computational work when large-scale mathematical models are handled on computers. Therefore, it is important to be able to solve such problems efficiently. It is assumed that the systems which must be solved many times during the treatment of the models, are (i) very large (containing more than equations) and (ii) general sparse. Moreover, it is also assumed that parallel computers with shared memory are available. An efficient algorithm for the solution of such large systems under the above assumptions is described. Numerical examples are given to demonstrate the ability of the algorithm to handle very large systems of linear algebraic equations. The algorithm can be applied in the treatment of some large-scale air pollution models without using splitting procedures.
1 Motivation Large-scale air pollution models can successfully be used to resolve many tasks connected with the selection of appropriate measures that could be applied in the efforts to avoid possible damages caused by harmful pollutants. Some of these tasks are legislated in official documents of the Parliament of the European Union (see, for example, [3]). Most of the large-scale air pollution models are described by systems of partial differential equations (the number of equations being equal to the number of chemical species studied by the model); see [1, 8, 18, 19]. The direct application of either finite elements or finite differences during the numerical treatment of such models leads to the solution of very large systems of linear algebraic equations. Assume that the numbers of grid points along the coordinate axes is and respectively. Assume also that the number of chemical species is Several systems containing equations have to be treated at each time-step. If and then N = 80640000. Not only can N be very large (as shown in the above example), but also many time-steps are to be carried out. The number of time-steps is I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 53–64, 2004. © Springer-Verlag Berlin Heidelberg 2004
54
Zahari Zlatev
normally in the range from to Thus the computational tasks are very difficult both because of the computing time requirements and because of the storage needed. Most of the difficulties can be overcome by applying some splitting procedure. The large problem is split into a sequence of small problems, which can be treated on the available computers. The splitting procedures simplify very much the computational tasks. However, they are also causing splitting errors. It is difficult to control the size of these errors. This is why it is desirable to avoid (if possible) the application of splitting procedures. This can be done only if new and very efficient methods for the solution of very large systems of linear algebraic equations are developed and used. Some preliminary results obtained in the efforts to develop such methods will be discussed in this paper. The results are rather general and it will be possible to apply the new methods for the treatment of very large systems of linear algebraic equations also in some other fields of science and engineering.
2
Major Assumptions
Since the direct discretization of the systems of partial differential equations arising in air pollution modelling leads to the solution of large systems of linear algebraic equations, we shall assume that systems of the type
are to be solved. Matrix A is (i) very large (in this paper “very large” means that (ii) non-symmetric and (iii) very badly scaled, because some of the non-zero elements of A depend on concentrations of the chemical species, which vary in the range from to because these quantities are measured by using the number of molecules in cubic centimeter. Therefore, the direct use of iterative methods is not advisable. Matrix A is in general banded. However, when A is very large, then the bandwidth is also large and the use of direct methods for banded matrices is prohibitive (in spite of the fact that very efficient software for banded matrices is available; see [2]). Indeed, the bandwidth is about 168 000 when an air pollution model involving 35 species is discretized on a (480 × 480 × 10) grid. Matrix A is sparse. However, it is also difficult to exploit the sparsity directly, because of the great number of fill-ins which will be produced during the factorization even if a good pivotal strategy (as, for example, some of the pivotal strategies described in [15] and [17]) is used in the efforts to preserve better the original sparsity pattern of matrix A. This short analysis indicates that it is worthwhile to try the following approach. Apply some good method for factorization of sparse matrices combined with dropping of all non-zero elements which are smaller than a given droptolerance parameter multiplied by the maximal in absolute value element in the row to which the candidate for dropping belongs. An approximate LUfactorization will be calculated in this way (the method is fully described in [7, 16, 17]). The approximate LU-factorization of matrix A can then be used as a
Parallel Solution of Very Large Sparse Systems
55
preconditioner for some iterative method (as, for example, some of the methods discussed in [4, 5, 9–14, 16, 17]). The calculation of the preconditioner remains the most time-consuming part in the solution of (1) also when dropping is used during the factorization in order to preserve better the sparsity pattern of matrix A. Therefore, it is important to develop a parallel algorithm for the computation of the preconditioner in which the ideas sketched in the previous paragraph can efficiently be applied. The development of such a parallel algorithm is discussed in this paper.
3
Description of the Algorithm
The algorithm used to obtain an approximate LU-factorization of matrix A (that can be used as a preconditioner in the solution of the system of linear algebraic equations by some iterative method), consists of the following five steps.
3.1
Step 1 – Obtaining an Upper Block-Triangular Matrix
A simple reordering is performed in an attempt to push the non-zeros in the lower triangular part of matrix A as close to the main diagonal as possible. First the columns of A are ordered. Let be the number of non-zeros in column Column interchanges are applied to obtain a permutation of A such that
After that the rows are ordered in a similar way. Assume that is the number of non-zeros in row Row interchanges are applied to obtain a permutation (of the matrix obtained after the column interchanges) such that
The result of the column and row interchanges performed as described above is a matrix in which many non-zero elements are moved to the lower left-hand corner of the matrix and, thus, the matrix obtained after these interchanges can be considered as an upper block-triangular matrix. Some other reordering algorithms can also be used. For example, the algorithm LORA from [6] can be applied. The advantage of the algorithm sketched above is that it is very cheap; its computational cost is O ( N Z ) , where NZ is the number of non-zeros in A. The computational cost of LORA is O(NZ log N) which is a considerable increase when N is very large. On the other hand, a more expensive computationally, but also more advanced, algorithm (such as LORA) may lead to a better reordering of the matrix and, thus, to a better performance in the remaining steps of the algorithm.
3.2
Step 2 – Dividing the Reordered Matrix into Block-Rows
The reordered, as described in the previous sub-section, matrix can be divided into several block-rows the diagonal blocks of which are rectangular matrices.
56
Zahari Zlatev
Denote the reordered matrix by B (i.e. B = PAQ, where P and Q the permutation matrices that are induced by the row and column interchanges). It is desirable to divide matrix B into block-rows which can be processed in parallel. A simple example for such a division with is given in Fig. 1. While
Fig. 1. Division of matrix B when the special case is used both in Fig. 1 and in the other figures (in order to facilitate the understanding of the ideas), all remarks given below are for the general case (i.e. for an arbitrary Note that all the blocks located under the diagonal blocks where contain only zero elements. This is essential in the attempts to achieve parallel computations when the different block-rows are processed. It should also be noted that the diagonal blocks are rectangular. The number of rows is greater than or equal to the number of columns for the first diagonal blocks. The situation is changed for the last diagonal block i.e. the number of columns is less than or equal to the number of rows. The computations in each block-row are independent of the computations in the remaining block-rows. This means that there are parallel tasks related to the computations in the next step (Step 3). It is important to emphasize here that an attempt to produce block-rows with approximately equal numbers of rows is carried out in order to achieve a better loading balance. The fact that rectangular diagonal blocks with are allowed facilitates this task. However, a perfect loading balance will in general not be achieved even if the numbers of the rows in all block-rows are the same (because the numbers of non-zero elements may vary from one block-row to another). Therefore, (where is the number of processors which are to be assigned to the job) is used in the experiments in Section 4 in order to increase the possibility of achieving a better loading balance.
3.3
Step 3 – Factorizing the Block-Rows
Gaussian transformations are carried out in order to produce zero elements under the main diagonal of each diagonal block These calculations can be performed in parallel. The result of performing Gaussian transformations for the matrix given in Fig. 1. is shown in Fig. 2. While the special case is used in Fig. 2 in order to facilitate the understanding of the ideas, the remarks given below are for the general case (i.e. for an arbitrary It is seen (compare Fig. 2 with Fig. 1) that each of the first block-rows of matrix B is divided into two block-rows. Consider the diagonal row-block
Parallel Solution of Very Large Sparse Systems
57
Assume that this diagonal block contains rows and columns. Then, as a results of the Gaussian transformations in row-block the diagonal block is split to an upper triangular matrix and a zero matrix of order Consider block and assume that it contains rows and columns with The results of performing Gaussian transformation in row-block will lead to an upper triangular matrix
Fig. 2. The result of the factorization of the block-rows of the matrix given in Fig. 1. The dimensions of the remaining blocks in Fig. 2 are listed below:
and and
with with with with
The computations related to the blocks and as well as the computations related to the blocks are finished at the end of Step 3. The further computations are carried out in the remaining blocks. Therefore, it is desirable that these blocks are small (the reordering procedure from Step 1 is performed in attempt to reduce as much as possible the size of these blocks).
3.4
Step 4 – Producing Zeros in Blocks
The computations should be continued by producing zeros in the blocks with and It is appropriate to carry out the calculations by “diagonals”. During the calculations along the “first diagonal”, the pivotal elements of block are used to produce non-zeros in the pivotal elements of are used to produce non-zeros in and so on. The number of tasks along the “first diagonal” is and these tasks can be performed in parallel. When the calculations along the “first diagonal” are finished, the calculations along the “second diagonal” can be started. The pivotal elements of block are used to produce non-zeros in the pivotal elements
58
Zahari Zlatev
of are used to produce non-zeros in and so on. The number of parallel tasks is now The calculations are carried out in a similar manner along the “remaining diagonals”. It is important to emphasize that the number of parallel tasks is reduced by one when the calculations along the next diagonal are to be carried out. This is not a big problem when the blocks are small. In order to improve the performance it is worthwhile to choose the number of block-rows considerably larger than the number of processors that will be used (this is another reason for choosing the first one was discussed in the end of When the calculations in Step 4 are completed, the matrix shown in Fig. 2 will be transformed so that the structure given in Fig. 3 will be obtained. As
Fig. 3. The result of producing zeros in the blocks
of the matrix given in Fig. 2.
mentioned above, the number of parallel tasks is gradually reduced when the calculations are carried out by “diagonals”. Parallel computations can also be achieved in the following way. Consider any block and The production of zeros in any row of this block (by using the pivotal elements of block is a parallel task. This means that the computations in each row of block can be carried in parallel. The parallel tasks are not so large as in the previous case (where zeros in whole blocks are produced). However, the tasks are still sufficiently large when matrix A is very large. Moreover the possibility of achieving a better loading balance is in general increased, because the number of parallel tasks is very large. The second approach is used to obtain the results shown in Section 4.
3.5
Step 5 – Reordering and Finishing the Computations
The matrix, which structure is shown in Fig. 3, can be reordered (by row permutations) to the form given in Fig. 4. It should be emphasized here that it is not necessary to perform the actual row interchanges, it is quite sufficient to renumber the rows. The large block formed by the blocks and the appropriate zero blocks is an upper triangular matrix. The order of this large block is
Parallel Solution of Very Large Sparse Systems
59
Fig. 4. The result of reordering the blocks in the matrix given in Fig. 3.
The column-block formed by the blocks is a rectangular matrix. It is clear that the first dimension of this block is the same as that of the square matrix formed by the blocks which is given in (4). The second dimension of this matrix is Simple calculations show that the matrix formed by the blocks is square. Its order is Furthermore, this matrix is normally not very large. Furthermore, it should be expected that this matrix is relatively dense, because a lot of computations involving the blocks have already been carried out in the previous steps. Therefore, it is worthwhile to switch to dense matrix technique in Step 5 and to apply subroutines from, for example, [2].
4
Numerical Results
The numerical algorithm discussed in the previous sections has been tested by using different matrices produced by the matrix generators described in [17]. There are several advantages when such generators are used: (i) one can produce arbitrarily many matrices (while the number of test-matrices in the available data-bases is limited), (ii) one can vary the size of the matrices, (iii) one can vary the sparsity pattern, (iv) one can vary the number of non-zero elements and (v) one can vary the condition number of the matrices tested. A few experiments will be given in this section to demonstrate the performance of the algorithm in the following situations. The behaviour of the numerical algorithm when the number of block-rows is varied for very large matrices is different from the corresponding behaviour for small matrices. It should be noted that matrices of order are called here small. Such matrices are considered as large in many papers on the solution of sparse systems of linear algebraic equations. The parallel properties of the algorithm. The conclusions drawn in this section and in the next one are based on results obtained in much more experiments, than those used in the preparation of Table 1–Table 3.
60
Zahari Zlatev
Some attempts to simulate matrices which arise after the discretization of air pollution models were made: (i) the average number of non-zero elements per row was no less than 10, (ii) the non-zero elements were widely spread and (iii) the matrices chosen for experiments were badly scaled. All experiments, which are reported here were carried out on SUN computers at DCSC (the Danish Center for Scientific Computing). Some experiments on IBM computers at the University of Aarhus gave quite similar results.
4.1
Varying the Number of Block-Rows for Small Matrices
Systems containing linear algebraic equations are used in this sub-section. The number of the non-zero elements is 1 000 110 (i.e. the average number of non-zero elements per row is about 10). The number of block-rows is varied in the range from 8 to 512. The results are shown in Table 1 (the computing times are given in seconds). Computing times measured in seconds are also used in the remaining tables (Table 2 and Table 3). The notation that is applied in all the tables can be explained as follows: ORD time is the sum of the time needed for the reordering of the matrix (described in Step 1; see Section 3) and the time needed to divide the matrix into block-rows (Step 2). FACT time is the time needed to obtain the approximate LU-factorization, which is used as a preconditioner in the solution part (the preconditioner is calculated in Step 3 - Step 5 in Section 3). SOLV time is the time needed to obtain a starting approximation for the iterative procedure (the back substitution step) and, after that, to carry out iterations until a prescribed accuracy (an accuracy requirement of was actually used in all experiments) is achieved by the preconditioned iterative method chosen (the modified Orthomin method from [17] was actually used in all runs). TOTAL time is the total computing time spent in the run. Several conclusions can be drawn by studying the results in Table 1 (similar conclusions can be drawn by using the results of many other runs which were performed). 1. The ORD times and the SOLV times do not depend too much on the parameter (on the number of block-rows). 2. The FACT times (and, therefore, also the TOTAL times) depend on the choice of For this matrix, the best result is obtained with the choice 3. When the FACT time is the best one (i.e. when the SOLV time are comparable with the FACT time.
4.2
the ORD time and
Varying the Number of Block-Rows for Large Matrices
The number of equations in the system of linear algebraic equations is increased 40 times, i.e. from 100000 to 4000000. The number of non-zero elements in the
Parallel Solution of Very Large Sparse Systems
61
matrix is increased from 1000110 to 40000110, i.e. the average number of nonzero elements per row is again about 10. This very large system is solved by using different values of Results are shown in Table 2. Similar conclusions, as those drawn in the previous sub-section, can be drawn by studying the results in Table 2 (it should again be emphasized that the results obtained in many other runs show the same trends).
1. It is clearly seen that both the ORD times and the SOLV times practically do not depend on the parameter (on the number of block-rows). 2. The FACT times (and, therefore, also the TOTAL times) depend on the choice of For this matrix, the best result is obtained with the choice 3. The FACT time is the largest part of the TOTAL time also with the best choice of (i.e. when
4.3
Parallel Runs
The system used in the previous section (i.e. the system with 4000000 equations and with 40000110 non-zero elements in its coefficient matrix) was also run on four processors. Results are shown in Table 3. Not only are the computing times
62
Zahari Zlatev
shown in Table 3, but also the speed-up factors are given there (in brackets). The speed-up factors are calculated by taken the ratios of the computing times obtained in the runs on one processor (these times are given in Table 2) and the computing times obtained on four processors.
The results that are given in Table 3 (as well as the results obtained in many other runs) indicate that the following conclusions can be drawn.
1. The ORD times and the SOLV times remain practically the same when parameter (i.e. the number of block-rows) is varied. 2. The FACT times (and, therefore, also the TOTAL times) depend again on the choice of For this matrix, the best result is obtained with the choice 3. The ORD time and the SOLV time remain considerably smaller than the FACT time also when the FACT time is the smallest one (i.e. for the best choice of 4. The speed up factors for the ORD times remain practically the same for all values of These factors are also very small. This shows that the ordering of matrix and the division to row-block are two operations which are in fact run sequentially. 5. Also the speed up factors for the SOLV times remain practically the same for all values of These factors are greater than the corresponding factors for the ORD times, but still not very large. This shows that the back substitution and the iterations during the preconditioned modified Orthomin algorithm do not parallelize very well. 6. The speed up factors for the FACT times tend to decrease when the value of is increased (i.e. when the matrix is divided into more block-rows). These factors are greater than the corresponding factors for the ORD times and the SOLV times. The efficiency achieved (i.e. the speed-up factor divided by the number of processors and multiplied by 100) is very often over 90% (about 94% for the best choice
Parallel Solution of Very Large Sparse Systems
63
7. Also the speed up factors for the TOTAL times tend to decrease when the value of is increased (i.e. when the matrix is divided into more block-rows). These factors are smaller than the corresponding factors for the FACT times, but considerably greater than the correspond factors for the ORD times and the SOLV times. The efficiency achieved is often over 90%. However, for the important case where the best choice is made the efficiency is considerably smaller; about 71%.
5
Conclusions
An algorithm for the solution of very large sparse systems of linear algebraic equations was discussed and tested. Several conclusions about the performance of the algorithm (including the performance on a SUN parallel computer) were drawn in the previous section. Some additional improvements are needed in order to apply this algorithm in the treatment of large-scale mathematical models for studying air pollution phenomena. It is necessary to improve the performance of the following parts of the algorithm: the reordering part, the division into block-rows the preconditioned iterative methods. It might be worthwhile to try to exploit some special properties of the systems of linear algebraic equations arising in large scale air pollution models in order to find a simpler and more efficient preconditioner.
Acknowledgements Two grants (CPU-1002-27 and CPU-1101-17) from the Danish Centre for Scientific Computing (DCSC) gave us access to the IBM computers at the Århus University and the SUN computers at the Technical University of Denmark. The members of the staff of DCSC helped us to resolve some difficult problems related to the efficient exploitation of the grids of IBM and SUN computers.
References l. Alexandrov, V., Sameh, A., Siddique, Y., and Zlatev, Z.: Numerical integration of chemical ODE problems arising in air pollution models. Environmental Modelling and Assessment, Vol. 2 (1997), 365-377. 2. Anderson, E., Bai, Z., Bischof, C., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Ostrouchov, S., and Sorenson, D., LAPACK: Users’ guide, SIAM, Philadelphia, 1992. 3. Directive 2002/3EC of the European Parliament and of the Council of 12 February 2002 relating to ozone in ambient air. Official Journal of the European Communities, Vol. L 67 (2002), pp. 14-30.
64
Zahari Zlatev
4. Eirola, T. and Nevanlinna, O.: Accelerating with rank-one updates. Lin. Alg. Appl., Vol. 121 (1989), pp. 511-520. 5. Freund, R. W.: A transpose-free quasi-minimal residual algorithm for nonHermitian linear systems. SIAM J. Sci. Stat. Comput., Vol. 14 (1993), pp. 470-482. 6. Gallivan, K., Hansen, P. C., Ostromsky, Tz., and Zlatev, Z.: A locally optimized reordering algorithm and its application to a parallel sparse linear system solver. Computing, Vol. 54 (1995), pp. 39-67. 7. Gallivan, K. A., Sameh, A. H., and Zlatev, Z.: A parallel hybrid sparse linear system solver. Computing Systems in Engineering, Vol. 1 (1990), pp. 183-195. 8. Havasi, A. and Zlatev, Z.: Trends of Hungarian air pollution levels on a long timescale. Atmospheric Environment, Vol 36 (2002), 4145-4156. 9. Saad, Y. and Schultz, M. H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., Vol. 7 (1986), pp. 856-869. 10. Sonneveld, P.: CGS, a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., Vol. 10 (1989), pp. 36-52. 11. Vinsome, P.: ORTHOMIN, an iterative method for solving sparse sets of simultaneous linear equations. Proc. Fourth Sympos. on Reservoir Simulation, Society of Petr. Eng. of AIME (1976) 12. Vorst, H. A. van der: BI-CGSTAB: A fast and smoothly converging variant of BICG for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., Vol. 13 (1992), pp. 631-644. 13. Vuik, C. and Vorst, H. A. van der: A comparison of some GMRES-like methods. Lin. Alg. Appl., Vol. 160 (1992), pp. 131-160. 14. Yang, U. M. and K. Gallivan, K.: A Family of Preconditioned Iterative Solvers for Sparse Linear Systems. Applied Numerical Mathematics, Vol. 30 (1999), pp. 155-173. 15. Zlatev, Z.: On some pivotal strategies in Gaussian elimination by sparse technique. SIAM J. Numer. Anal., Vol. 17 (1980), pp. 18-30. 16. Zlatev, Z.: Use of iterative refinement in the solution of sparse linear systems. SIAM J. Numer. Anal, Vol. 19 (1982), pp. 381-399. 17. Zlatev, Z.: Computational methods for general sparse matrices. Kluwer Academic Publishers, Dordrecht-Boston-London (1991) 18. Zlatev, Z.: Computer treatment of large air pollution models. Kluwer Academic Publishers, Dordrecht-Boston-London (1995) 19. Zlatev, Z., Dimov, I. Ostromsky, Tz. Geernaert, G., Tzvetanov, I. and BastrupBirk, A.: Calculating losses of crops in Denmark caused by high ozone levels. Environmental Modelling and Assessment, Vol. 6 (2001), 35-55.
Part II
Recent Achievements in Preconditioning
This page intentionally left blank
Solution of Robust Linear Regression Problems by Krylov Subspace Methods Venansius Baryamureeba Institute of Computer Science, Makerere University, P.O. Box 7062, Uganda
[email protected],
[email protected] http://www.ii.uib.no/~barya, http://www.makerere.ac.ug/ics
Abstract. Several methods have been suggested for obtaining the estimates of the solution vector for the robust linear regression model using an iteratively reweighted criterion based on weighting functions, which tend to diminish the influence of outliers. We consider a combination of Newton method (or iteratively reweighted least squares method) with a Krylov subspace method. We show that we can avoid preconditioning with A preconditioner by merely transforming the sequence of linear systems to be solved. Appropriate sequences of linear systems for sparse and dense matrices are given. By employing efficient sparse QR factorization methods, we show that it is possible to solve efficiently large sparse linear systems with an unpreconditioned Krylov subspace method.
1 Introduction Consider the standard linear regression model where is a vector of observations, is the data or design matrix of rank is the vector of unknown parameters, and is the unknown vector of measurement errors. Let the residual vector be given by
where
denotes the
row of A. In this paper we need to solve
where is a given weighting function, and is the scale factor (connected to the data). The functions we are interested in are those that are less sensitive to large absolute residuals. The functions we will consider are twice continuously differentiable almost everywhere with Baryamureeba [1] recently suggested the Barya function
I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 67–75, 2004. © Springer-Verlag Berlin Heidelberg 2004
68
where
Venansius Baryamureeba
and
are problem-dependent parameters. Huber [8] sug-
gested the Huber function
where
dependent parameter. The Logistic function is proposed the Fair function posed the function
is a problemFair [6]
Huber [8] also prowhich is given the name Talwar
[7]. The Barya function is a linear combination of the Talwar and LSQ weighting functions. In particular, let and denote the Barya, LSQ and Talwar functions respectively. Then The parameter must be chosen to satisfy two conflicting goals: (i) to guarantee a positive definite weight matrix and (ii) to minimize the influence of large absolute residuals. Let where and are the piece-wise sub-domains over which the Barya function is defined. It is clear that the Barya function is strictly convex in any sub-domain It is also continuous over the entire domain Thus we refer to the Barya function as a piece-wise convex function.
1.1
Problem Formulation
For a known
the first order conditions for (2) are:
where is an with elements Newton’s Method Approach. One of the methods for solving the nonlinear problem (4) is Newton’s method. Given an initial guess we compute a sequence of search directions and iterates as follows:
where is a diagonal matrix with diagonal elements and is a step-length parameter. We remark that when is positive definite, can be formulated as a weighted least squares problem Iteratively Reweighted Least Square (IRLS) Method. The IRLS linear system corresponding to (4) differs from the Newton equation (5) in the weight matrix G. For IRLS method Approach. On the other hand, Scales et al. [11] suggest another formulation of IRLS algorithm based on the optimization problem: By setting the derivative of this problem to zero, we get the generalized normal equation
Solution of Robust Linear Regression Problems by Krylov Subspace Methods
for
69
is defined in (1) and G is the diagonal matrix defined by
where we choose Active Set Method. Let
sufficiently small. be defined by
where is given by (1). For the Talwar function, the influence of large absolute residuals is reduced drastically from both the right hand side and the coefficient matrix since and for all Observe that IRLS method and Newton method are equivalent for this function since for all Hence, Newton’s method based on the Talwar function does not require a line-search when a direct method is used. Do we need a line-search when we carry out inexact computation? Interestingly, it has been shown [1] that the Talwar approach is an active set method (c.f. simplex method) where elements of corresponding to small absolute residuals form the basic variables and those corresponding to large absolute residuals form the nonbasic variables.
2
IRLS Method Based Comparative Study
The Barya and Huber Functions. Recall that IRLS method based on the Huber function is globally convergent [9] and no line-search is necessary with exact computation (direct method). For the Barya function, IRLS method is equivalent to Newton’s method. Here we compare the Barya and Huber functions at a given iteration of IRLS method. The purpose of this comparison is to determine the choice of the parameter in (3). Let defined by (8) be generated by IRLS method based on the Huber function at a given iteration. Let be such that
Let
be a diagonal matrix with diagonal elements
70
Then
Venansius Baryamureeba
Let
be diagonal matrices with diagonal elements
Then H = KG. Thus we have:
Let
Then the weighted problems corresponding to I and II are:
since G and K are positive definite diagonal matrices. To be able to reduce the influence of large absolute residuals it is clear from comparing (9) and (10), (11) and (12) that for all Thus we suggest to choose in (3) by
A natural choice of is 1. In this paper we set It is clear from (13) and (14) that the IRLS method based on the Barya function reduces the influence of large absolute residuals more than IRLS method based on the Huber function. Since IRLS method and Newton method are equivalent for the Barya function, IRLS method based on the Barya function exhibits quadratic convergence [5] near the solution. This is supported by the numerical tests in [3]. Recall that the Barya function is a linear combination of the Talwar and least squares functions. The parameter must be kept small (usually because of the need to minimize the bound on the spectral condition number of the (preconditioned) coefficient matrix and also to keep iterates away from the boundary of the feasible region. A line-search procedure is not necessary for IRLS method (or Newtons’s method) based on the Barya function. For inexact Newton method based on the Barya function, if the search directions are computed to low accuracy then we need to do a line-search so that is decreased substantially. Since the Barya function is a piece-wise convex function the line-search based on decreasing in (2) will always lead to a local minimum in the desired region
Solution of Robust Linear Regression Problems by Krylov Subspace Methods
71
Block Form of the Barya Function. Matrix K in (14) is a scale matrix. The IRLS method based on the Barya function may be interpreted as applying IRLS method based on the Huber function to the scaled problem where the scale matrix is carefully chosen to minimize the influence of large absolute residuals. Results (12) and (14) show that it is possible for weight matrix H (corresponding to the Barya function) to have at least two distinct diagonal elements. We only need to ensure that for all Let be given by (8) and Define for and Then we define the block form of the Barya weighting function by
In practice we require that the weight matrix H in (12) to have few distinct diagonal elements. Thus we choose in (15) to be small. On the other hand it is easy to show that
Since
we can see that Thus Newton’s method and IRLS method are equivalent for this block form of the Barya function.
3
Solving the Sequence of Linear Systems
Any robust linear regression problem can be posed as a sequence of weighted linear systems and solved by either a direct method or iterative method or both.
3.1
Iterative Method Approach
Lemma 1. Let Let a diagonal matrix with each diagonal element equal to 1 or for Then For the proof see [1]. Unpreconditioned Linear System. Consider equation (5). Let
be
72
where
Let
Venansius Baryamureeba
is such that (Q consists of orthogonal columns) and is a nonsingular upper triangular matrix. Given (16), (5) simplifies to
Instead of solving (17) we solve the symmetric system
and then compute by Preconditioning with Matrix. Here we consider preconditioner [4]. Considering system (5), the preconditioned linear system can be written as
Next we consider the preconditioned matrix factorization (16)
Given the QR
By similarity transformations the matrices and are similar and thus We note that if G is a positive definite diagonal matrix then see [1]. Thus from a theoretical point of view it is evident that preconditioning with is unnecessary. In other words, instead of solving (5) with preconditioner one should solve (18) with an unpreconditioned iterative method, for instance unpreconditioned conjugate gradient method. The major draw back of solving (18) is that for a sparse matrix A, Q is often nearly full (dense). The general results on the upper bound of the spectral condition of the preconditioned matrix are given in [3] and [4]. Similar results for can be derived by simply observing that Least Squares Approach. When G is positive definite then (18) corresponds to the weighted least squares problem
A good and generally available reliable solver like LSQR can applied to (21). Linear systems arising from Newton method based on the Barya, Fair, and Logistic functions can be formulated in the form (21). Recall that for the Talwar function and for all Thus, for the Talwar function, (18) can be formulated as a least squares problem of the form (21) if and only if is positive definite, whereas it is not possible to formulate (5) in the form (21) for the Huber function since and for all Iteratively Reweighted Least Squares (IRLS) Method. Since G is positive definite for IRLS method, (5) & (6) can be formulated in the form (21). Related Work. Let G be a diagonal weight matrix and AQ be given by (16). Scales et al. [11] used Conjugate Gradient (CG) method to solve linear systems of the form
Solution of Robust Linear Regression Problems by Krylov Subspace Methods
73
O’Leary [10] used CG method to solve linear systems of the form
In [3] and [4] preconditioned CG method was used to solve linear systems of the form (22) with as preconditioner. In [4] and [10], a line-search procedure was used to determine the step-length when Newton’s method based on the Talwar function was used. The following observations are now in order:
1. For a dense data matrix A, if unpreconditioned CG method is used, it should be used on system (23) instead of system (22). When the weight matrix G is positive definite, the alternative approach is to solve the corresponding weighted least squares problem. Furthermore, for a dense data matrix A , instead of solving linear systems of the form (22) with as preconditioner, we suggest solving linear systems of the form (23) with unpreconditioned CG method. 2. For sparse data matrix A, we note that the factor Q may not be as sparse as A. Thus there is need to compute the density For an matrix X we define the density At the beginning of the iteration process we need to compute the densities of A, Q and R using (24). We then estimate the cost per iteration for solving (23) with unpreconditioned CG method and the cost for solving (22) with preconditioner. We use these relative costs when determining the linear system to be solved. Alternatively, we can compute the cost of one iteration for (22) with preconditioner and for (23) with unpreconditioned iterative method and then continue with the linear system that is less costly. We may add that with emerging efficient sparse QR factorization methods, the choice between solving (23) with unpreconditioned CG method and (22) with preconditioned CG method depends heavily on numerical results other than theoretical results. 3. Newton’s method based on the Talwar function should be used without linesearch and the solution to the linear system should be computed to high accuracy. We remark that for a positive definite weight matrix G solving the least squares problem corresponding to (23) with for example LSQR may be worthwhile.
3.2
Mixed Method Approach
We consider solving the sequence of linear systems by combining a direct method and an iterative method in some manner, see [2]. The idea is to utilize the factorization from the previous iteration in constructing the preconditioner for the current linear system. There are situations when preconditioning is necessary. For instance when is very large for G positive definite or when is very large for G positive semi-definite. For a discussion on low-rank correction preconditioners see[1].
74
Venansius Baryamureeba
4
Numerical Comparison
The data matrices are sparse random matrices as described in Table 1. We use the matlab sparse function to compute the QR factorization A = QR. We observe that where is a nonsingular upper triangular matrix. Table 1 shows that for A sparse, Q may be either sparse or dense. Since the problems we are interested in are large and sparse, iterative methods may be efficient if we solve the sparse linear system. Thus, it is necessary that we compute the densities for A and Q at the beginning of the iterative process. Otherwise, we need to compute the cost of one iteration for the linear system in A and also for the linear system in Q and then compare the costs.
5
Concluding Remarks
(Un)preconditioned Krylov subspace methods have been combined with Inexact Newton Method to solve robust linear regression problems. This paper sheds more light on when a line-search with Inexact Newton Method is (not) necessary. We have suggested new approaches that can be used to efficiently solve robust linear regression problems.
References 1. Baryamureeba, V.: The impact of equal-weighting of both low-confidence and highconfidence observations on robust linear regression computation. BIT. 41 (2001) 847–855. 2. Baryamureeba, V.: Solution of large-scale weighted least squares problems. Numerical Linear Algebra with Applications, 9 (2002) 93–106. 3. Baryamureeba, V.: Solution of robust linear regression problems by preconditioned conjugate gradient type methods. Technical Report No. 187, Department of Informatics, University of Bergen, 5020 Bergen, Norway, March 22, 2000. 4. Baryamureeba, V., and Steihaug, T: On the properties of preconditioners for robust linear regression. Technical Report No. 184, March 2000, Department of Informatics, University of Bergen, Norway. Journal of Opt. Theory and Appl. (to appear) 5. Dembo, R.S., Eisenstat, S.C., and Steihaug, T.: Inexact Newton methods. SIAM Journal of Numerical Analysis. 19 (1982) 400–407. 6. Fair, R.C.: On the robust estimation of econometric models. Ann. Econ. Social Measurement. 3 (1974) 667–678.
Solution of Robust Linear Regression Problems by Krylov Subspace Methods
75
7. Hinich, M.J., and Talwar, P.P.: A simple method for robust regression. J. Amer. Statist. Assoc. 70 (1975) 113–119. 8. Huber, P.J.: Robust estimation of a location parameter. Annals Math. Statist. 35 (1964) 73 –101. 9. Huber, P.J.: Robust statistics. J. Wiley, New York. (1981). 10. O’Leary, D.P.: Robust regression computation using iteratively reweighted least squares. SIAM Journal of Matrix Analysis and Applications. 11 (1990) 466–480. 11. Scales, J.A., Gersztenkorn, A., and Treitel, S.: Fast solution of large, sparse, linear systems: Application to seismic travel time tomography. Journal of Computation Physics. 75 (1988) 314–333.
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov Central Laboratory for Parallel Processing, Bulgarian Academy of Sciences Acad. G. Bontchev, Bl. 25A, 1113 Sofia, Bulgaria {gery,john,margenov}@parallel.bas.bg
Abstract. The studied large-scale linear problems arise from CrouzeixRaviart non-conforming FEM approximation of second order elliptic boundary value problems. A two-level preconditioner for the case of coefficient anisotropy is analyzed. A special attention is given to the potential of the method for a parallel implementation. Keywords: Non-conforming FEM, preconditioning, parallel algorithms.
AMS Subject Classifications: 65F10, 65N30.
1 Introduction We consider the elliptic boundary value problem
where
is a convex polygonal domain in is a given function in is a symmetric and uniformly positive definite matrix in is the outward unit vector normal to the boundary and We assume that the entries are piece-wise smooth functions on In the paper we use the terminology of the flow in porous media and we refer to as a pressure and as a velocity vector. The problem (1) can be discretized by the finite volume method, the Galerkin finite element method (FEM), conforming or non-conforming, or the mixed FEM. Each of these methods has its advantages and disadvantages when the problem (1) is used in a particular application. In [2] Arnold and Brezzi have demonstrated that after the elimination of the velocity and pressure unknowns the obtained Schur system for the Lagrange multipliers is equivalent to a discretization of (1) by Galerkin method using linear non-conforming finite elements. Namely, in [2] it is shown that the lowest-order Raviart-Thomas mixed finite element approximations are equivalent to the usual Crouzeix-Raviart non-conforming linear finite element approximations when the non-conforming space is augmented with cubic bubbles. Further, such a relationship between the mixed and nonconforming finite element methods has been studied and simplified for various I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 76–84, 2004. © Springer-Verlag Berlin Heidelberg 2004
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems
77
finite element spaces (see, e.g. [1,5]). The work in this direction resulted also in construction of efficient iterative methods for solving mixed FE systems (see, e.g., [6–8]). Furthermore, the stiffness matrix has a regular sparsity structure such that in each row the number of non-zero entries is at most five. This paper provides a continuation of the study recently published in [12]. Here, the sparsity pattern of the approximation algorithm is changed to handle the case of coefficient anisotropy. The study is also related to the parallel techniques from [4, 10], where MIC(0) preconditioning of linear conforming and rotated bilinear non-conforming finite elements is considered. The rest of the paper is organized as follows. In Sections 2 and 3 we introduce the finite element approximation and the two-level algorithm. In Section 4 we propose a locally optimized anisotropic sparse approximation B of the Schur complement S. The condition number is uniformly estimated. Next, in Section 5 we derive expression for the execution time on a multiprocessor computer system which shows a good parallel efficiency for large scale problems. Numerical tests of the PCG convergence rate are presented in Section 6 where the system size and the anisotropy ratio are varied. At the end, short concluding remarks are given.
2
Finite Element Discretization
The domain is discretized using triangular elements. The partition is denoted by and is assumed to be quasi-uniform with a characteristic mesh-size It is aligned with the discontinuities of the coefficient matrix, so that over each element the function is smooth. Further, we assume that is generated by first partitioning into quadrilaterals Q and then splitting each quadrilateral into two triangles by one of its diagonals, see Figure 1. To simplify our considerations we assume that the splitting into quadrilaterals is topologically equivalent to a square mesh. We approximate the weak formulation of (1) using Crouzeix-Raviart non-conforming linear triangular finite elements. The FEM space consists of piece wise linear functions over determined by their values in the midpoints of the edges. The nodal basis functions of have a support on not more than two neighboring triangles where the corresponding node is the midpoint of their common side. Then the finite element formulation is: find satisfying
Here is defined as the integral averaged value of over each Now, the standard computational procedure leads to the linear system of equations
where A is the corresponding global stiffness matrix and is the vector of the unknown nodal values of The matrix A is sparse, symmetric and positive
78
Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov
definite. For large scale problems, the preconditioned conjugate gradient (PCG) method is known to be the best solution method. The goal of this study is to present a robust and parallelizable preconditioner for the system (3).
3 The Two-Level Algorithm Since the triangulation is obtained by diagonal-wise splitting of each cell Q into two triangles, see Figure 1-a, we can partition the grid nodes into two groups. The first group contains the centers of the quadrilateral super-elements and the second group contains the rest of the nodes. With respect to this splitting, A admits the following two-by-two block partitioning that can be written also in a block-factored form
where S stands for the related Schur complement. Obviously, is a diagonal matrix so that the Schur complement S can be assembled from the corresponding super-element Schur complements i.e.
where stands for the restriction mapping of the global vector of unknowns to the local one corresponding to a macroelement Q containing two triangles. Such a procedure is called static condensation. We now introduce the local Schur complement and its approximation
Here and In a very general setting, S and B are spectrally equivalent, if and have equal rowsums. The case corresponds to the isotropic approximation (see Figure 1-c). A particular case of this kind was proposed and analyzed in [12]. The dash lines represent the connectivity pattern of the Schur complement (see Figure 1-b) and its locally modified sparse approximations and (see Figure 1-c,d). Assembling the local matrices we get
After the static condensation step, the initial problem (3) is reduced to the solution of a system with the Schur complement matrix S. At this point we apply the PCG method with a preconditioner defined as a MIC(0) factorization (see, e.g., [3, 9]) of B, that is, This needs of course B to allow a stable MIC(0) factorization, which will be shown in Section 4.
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems
79
Fig. 1. (a) Node numbering of the super-element Q; (b) Connectivity pattern of (c) Connectivity pattern of (d) Connectivity pattern of
4
Locally Optimized Approximation for the Model Anisotropic Problem
The model anisotropic problem analyzed in this section is set on a uniform square mesh i.e. The coefficient matrix is macroelement-wise constant, and the anisotropy ratio is fixed, i.e. Then, the macroelement stiffness matrix and the related Schur complement are as follows:
Taking into account the symmetry arguments, we look for a locally optimized matrix (see (5)) in the form:
Consider now the local eigenvalue problem: find
The optimal value of the parameter condition number
such that
will minimize the local spectral
Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov
80
Obviously where Thus, (10) is reduced to a 3 × 3 eigenvalue problem and the related eigenvalues are:
Three cases are considered depending on the value of
namely:
The global condition number estimate follows directly from local one. The result of the presented analysis is summarized in the next theorem. Theorem 1. Consider the non-conforming FEM problem (2) on a square mesh. Let B is defined by (6) where are determined by (9) and the parameter satisfies the local optimality condition
Then:
(i) the sparse approximation B of the Schur complement S satisfies the conditions for a stable MIC(0) factorization; (ii) the matrices B and S are spectrally equivalent, where the following estimate for the relative condition number holds uniformly with respect to any possible coefficients’ jumps
5
Parallel Preconditioning Algorithm
The first step, i.e. the static condensation, is local and therefore can be performed fully in parallel. This is the reason to focus our attention on the PCG solution of the reduced system with the Schur complement S. Let us recall that the preconditioner was introduced as where D is the diagonal and L is the strictly lower triangular part of B. The computational complexity of one PCG iteration is given by
One can find some more details in [12] where a similar analysis for the isotropic case is made.
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems
81
MIC(0) is an inherently sequential algorithm where the solution of the arising triangular systems is typically recursive. We overcome this disadvantage by the proposed construction of the matrix B. For simplicity of the presentation we consider the model problem in on a square mesh with a mesh size (subsequently each cell is split into two triangles to get The structure of the matrices S and B is illustrated in Figure 2 where a column-wise numbering of the unknowns is used. A serious advantage of the introduced matrix B is that all of its diagonal blocks are diagonal. In this case, the implementation of the PCG solution step is fully parallel within each of these blocks.
Fig. 2. Sparsity pattern of the matrices S and B,
A simple model for the arithmetic and the communication times is applied (see, e.g., [13]) in the analysis of the parallel algorithm. We assume that: a) the execution of M arithmetic operations on one processor takes time where is the average unit time to perform one arithmetic operation on one processor (no vectorization), and b) the time to transfer M data elements from one processor to another can be approximated by where is the start-up time and is the incremental time necessary for each of M elements to be sent, and is the graph distance between the processors. Further, we consider a distributed memory parallel computer where the number of processors is and for some natural number The domain is split into equally sized strips where the processor is responsible for data and computations related to the strip. Then, we get the following expressions for the communication times related to and
The above communications are completely local and do not depend on the number of processors assuming that and are neighbors (see Figure 3). With are denoted the components which sends to and with - those
82
Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov
to The sign × indicates the place where the transferred components are stored. Although it is not mapped in the figure, the processor also have to receive the corresponding components from processors and This setting leads to the following expression for the parallel time per one PCG iteration
Fig. 3. Communication scheme for matrix-vector multiplication of systems with lower triangular and upper triangular
and for solution matrices.
Remark 1. From (15) we conclude that the parallel algorithm is asymptotically optimal. A more realistic analysis of the parallel performance needs more information about the behavior of the introduced average timing parameters and The key point here is that a good parallel scalability could be expected if
6
Numerical Tests
The numerical tests presented below illustrate the PCG convergence rate when the size of the discrete problem and the anisotropy ratio are varied in the test problem
A relative stopping criterion
is used
in the PCG algorithm, where stands for the residual at the iteration step, is the standard Euclidean inner product, and The computational domain is the unit square where homogeneous Dirichlet boundary conditions are assumed at the bottom side. A uniform mesh is used, where and the size of the discrete problem is
Two-Level Preconditioning of Crouzeix-Raviart Anisotropic FEM Systems
83
The qualitative analysis of the results given in Table 1 confirms that the number of iterations in all cases is namely, it grows proportionally to when is large enough. The influence of the anisotropy is in a full agreement with the theoretical estimate The last column is included in the table to show how important is to have a proper node-numbering following the direction of dominating anisotropy.
7
Concluding Remarks
In this paper we have proposed an anisotropic modification of the recently introduced two-level preconditioner for isotropic Crouzeix-Raviart FEM elliptic systems. The new construction allows efficient PCG solution of strongly anisotropic problems with fixed direction of dominating anisotropy. The new sparsity structure of the local matrices does not change the structure of the diagonal blocks of the global matrix B. The latter preserves the potential for efficient parallel implementation. One of the contributions of this paper is the locally optimized construction of where the minimal value of is realized in the interval given by Theorem 1. Our further plans include a generalization to 3-D problems on tetrahedral meshes. This is a much more complicated problem where symbolic methods could be needed to optimize the parametrized presentation of In this context we would refer to the results from [11] where an element preconditioning technique is reported for conforming linear FEM in 3-D. The structure of the Schur complement matrix S is the same as the element matrix for the rotated bilinear elements introduced by Rannacher and Turek. As a result, the parallel properties of the related algorithms are similar. Some representative results in this context can be found in [4] where the parallel times are analyzed in some more details and a set of numerical tests on distributed memory machines are presented.
Acknowledgements This work is supported by Center of Excellence BIS-21 grant ICA1-2000-70016, and the Bulgarian NSF Grants I-1001 and MU-I-901.
84
Gergana Bencheva, Ivan Georgiev, and Svetozar Margenov
References 1. Arbogast, T., Chen, Z.: On the implementation of mixed methods as nonconforming methods for second order elliptic problems. Math. Comp., 64 (1995) 943–972. 2. Arnold, D. N., Brezzi, F.: Mixed and nonconforming finite element methods: implementation, postprocessing and error estimates. RAIRO, Model. Math. Anal. Numer., 19 (1985) 7–32. 3. Blaheta, R.: Displacement decomposition — incomplete factorization preconditioning techniques for linear elasticity problems. Numer. Lin. Alg. Appl., 1 (1994) 107–126. 4. Bencheva, G., Margenov, S.: Performance analysis of parallel MIC(0) preconditioning of rotated bilinear nonconforming FEM systems. Mathematica Balkanica, 18 (2004) to appear. 5. Chen, Z.: Analysis of mixed methods using conforming and nonconforming finite element methods. RAIRO, Math. Model. Numer. Anal., 27 (1993) 9–34. 6. Chen, Z.: Equivalence between multigrid algorithms for mixed and nonconformning methods for second order elliptic problems. East-West J. Numer. Math., 4 (1996) 1–33. 7. Chen, Z., Ewing, R.E., Kuznetsov, Yu.A., Lazarov, R.D., Maliassov, S.: Multilevel preconditioners for mixed methods for second order elliptic problems. Numer. Lin. Alg. with Appl., 3 5 (1996) 427-453. 8. Chen, Z., Ewing, R.E., Lazarov, R.D.: Domain decomposition algorithms for mixed methods for second order elliptic problems. Math. Comp., 65 214 (1996) 467-490. 9. Gustafsson, I.: Modified incomplete Cholesky (MIC) factorization. In: D.J. Evans, ed., Preconditioning Methods; Theory and Applications, Gordon and Breach, (1984) 265–293. 10. Gustafsson, I., Lindskog, G.: On parallel solution of linear elasticity problems: Part I: Theory. Numer. Lin. Alg. Appl., 5 (1998) 123–139. 11. Langer, U.,Reitzinger, S.,Schicho, J.: Symbolic methods for the element preconditioning technique. Johanes Kepler University of Linz, SFB-Report No. 02-03 (2002) 12. Lazarov, R.D.,Margenov, S.D.: On a two-level parallel MIC(0) preconditioning of Crouzeix-Raviart non-conforming FEM systems. In: I. Dimov, I. Lirkov, S. Margenov, Z. Zlatev Eds., Numerical Methods and Applications. Lecture Notes in Computer Science, 2542, Springer Verlag, (2003) 192–201. 13. Saad, Y.,Schultz, M.H.: Data Communication in Parallel Architectures. Parallel Comput., 11 (1989) 131–150.
Parallel High Performance Computing on Composite Grids Roman Kohut Institute of Geonics, Academy of Sciences of the Czech Republic Studentská 1768, 70800 Ostrava-Poruba, Czech Republic
[email protected]
Abstract. The paper is concerned with the FE solution of the linear elastic BV problems on composite grids. Special interest is given to the implementation and numerical tests of both sequential and parallel codes.
1 Introduction This paper deals with the numerical solution of linear elasticity boundary value problems, which can be written in a weak form as follows:
Here is a Hilbert space of vector functions (see e.g. [4]). For the numerical solution of the problem (1) we use the finite element (FE) method on composite grids, which arise as a composition of (regular, structured) global coarse grid and (regular) local fine grid(s). The composite grid FE method starts with a global (coarse, regular) division of the domain For simplicity, we will consider a division of the domain into tetrahedrons. The division then enables us to define the standard FE space
where is in our case the set of linear polynomials. Further, let be a part of where the previous discretization should be refined and let be a finer discretization in which enables to define another FE space
Now, the composite grid FE space can be defined as
The composite grid FE space composite grid solution
can be then used for finding an approximate
I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 85–92, 2004. © Springer-Verlag Berlin Heidelberg 2004
86
Roman Kohut
Note that, in this construction, can consist of several separate parts. Moreover, the finer grid in can be further refined and so on, which gives the multilevel construction resulting in the composite grid space The paper completes results published in [1, 2] with numerical tests performed for 3D case. Tests are performed using both sequential and parallel codes.
2
The Iterative Solution of Composite Grid Problems
The decomposition (4) of the composite grid FE space can be used to construct iterative methods for solving the composite grid problem (5). Such a method was first introduced in [3]. The algorithm of this method, called FAC, is as follows: FAC method
Further, we will also use a symmetric version of FAC, which is obtained by adding another correction from the subspace to the beginning of each FAC iteration. This variant will be referred to as SFAC. The additive variant of FAC called JFAC (as the Jacobi-type method with damping), takes the form: JFAC method
These methods can be rewritten into an operator form which is more convenient for computer implementation. The composite grid FE problem can be then rewritten as the equation
with a symmetric positive definite operator A. The iterative methods FAC, JFAC and SFAC can be written as preconditioned Richardson’s iterations
Parallel High Performance Computing on Composite Grids
87
with
where and are the restriction and inclusion operators, respectively Since A is symmetric positive definite, the system (6) can be solved by the conjugate gradient method with preconditioning matrices or This preconditioning is implemented as the approximate solution of the system using one FAC (JFAC, SFAC) iteration starting from the zero initial guess.
3
Implementation
In this section, we focus on the implementation of the two–level composite grid FE method arising from the spaces and We shall start by introducing the standard FE bases in and respectively. Then we can introduce the subproblem matrices and right-hand side vectors as
For the implementation of the composite grid FE method, we must introduce some parameterization of the functions from the composite grid FE space V. In our case we use the nodal basis implementation for fully compatible global and local grids where is represented in the form
Here the first sum is taken over those coarse grid basis functions which have their support in The second sum is over all basis functions from The third sum is over the new basis functions corresponding to the coarse grid nodes lying on the interface The basis functions have zero values in all coarse and fine grid nodes with the exception of value 1 in one coarse grid node on and the values given by the interpolation in the corresponding fine grid nodes on This interpolation guarantees the continuity of the basis function See also Fig.1. Note that the nodal basis implementation in principle requires compatibility of the global and local grids only on the interface In the case of not fully compatible global and local grids, we seek the composite grid solution in the space where is the space of the functions, that have the form
88
Roman Kohut
Fig. 1. Nodal basis of the composite grid FE space
(13). Functions from V having a support in are used only for solving the subproblem on the coarse grid which is a part of the preconditioning matrix. For the implementation of the conjugate gradient method on composite grids and for the implementation of the FAC and JFAC iterative methods as preconditioners, we need procedures for a prolongation of the displacement which is realized by a linear interpolation, restrictions of the residual given by the transformation of nodal forces from fine grid nodes to coarse grid ones a computation of the residual implemented using elementby-element multiplications for the nodes lying on the interface and subproblem matrix and vector multiplications for the nodes outside the interface. a solution of the subproblems obtained by the conjugate gradient method with a preconditioning given by the displacementdecomposition (DiD) or the domain-decomposition (DD). Remark: In some real-life problems the coarse grid cannot resolve the fine distribution of materials. It means that
It was proved ([1]) that even in this case the FAC, SFAC and JFAC methods converge if we use a suitable damping. The numerical tests show ( see next section) that if we use these methods as preconditioning methods, the CG on composite grids may not converge.
Parallel High Performance Computing on Composite Grids
4
89
The Numerical Tests
Numerical tests were performed on two benchmark problems referred to as “MOST” problem and “Dolní Rožínka” problem.
I: The “MOST” Problem – A Bridge Pile under Loading This problem, which is illustrated in Fig.2, is formulated in a domain of size 37.2 × 37.2 × 31 metres. This domain contains a concrete pile of size 1.2 × 1.2 × 15 metres with elastic modulus E = 31.5 GPa, Poisson’s ratio and unit weight The pile is surrounded by an elastic clay with elastic modulus E = 19.88 MPa, Poisson’s ratio and unit weight The pile is loaded by a pressure V = 1.5 MPa. On the other sides of we assume zero normal displacements and zero tangential stresses. The global coarse grid has 32 × 32 × 32 nodes (98304 unknowns), the local fine grid uses halved grid sizes, the fine mesh has 23 × 23 × 41 nodes (65067 unknowns).
Fig. 2. “Most” problem
II: The “Dolní Rožínka” Problem – A Mining at the Uranium Ore Deposit This problem, which is illustrated in Fig.3, is formulated in a domain of size 1430 × 550 × 600 metres. The two basic materials in the problem domain are the uranium ore and the surrounding rock. These materials are assumed to be elastic with the same material constants – elasticity modulus E=2000 MPa, Poisson ratio and the unit mass The extracted volumes and their vicinity are filled by a goaf material. For the goaf material, we again assume a linear elastic behaviour with elastic constant E=2500 MPa, and
90
Roman Kohut
We use pure Dirichlet boundary conditions given by the solution of a pure Neumann problem modelling the pre-mining stress state. The global coarse grid has 124 × 137 × 76 nodes (3873264 unknowns), the local fine grid uses quater grid sizes, the fine mesh has 49 × 113 × 65 nodes (1079715 unknowns).
Fig. 3. “Dolní Rožínka” problem The numerical tests were done using both sequential and parallel codes. The sequential solution was performed on a workstation IBM RS/6000 43P-260 (the preconditioning for subproblems given by DiD), the parallel solution on a cluster of 9 PC’s with AMD Athlon 1.4 GHz 266MHz FSB processors (the preconditioning for subproblems given by DD). On the benchmark problems the following tests were performed: a) Tests on the preconditioners The tests were performed with five FAC-like preconditioners: 1. the nonsymmetric FAC starting from a fine grid 2. the symmetric FAC starting from a fine grid 3. the nonsymmetric FAC starting from a coarse grid 4. the symmetric FAC starting from a coarse grid 5. the additive FAC (JFAC) To test the parallel code, tests were done only on Benchmark II. The accuracy for CG on the composite grid was (see Table 1). The tests show that we can use succesfully the nonsymmetric preconditioners and that orthogonalization of the search directions is not necessary if we solve the subproblems more accurately The results for the JFAC preconditioner show that the “vertical” parallelization (the subproblems are solved in parallel) does not give any significantly improvement of the CPU time.
Parallel High Performance Computing on Composite Grids
91
b) Influence of the material inconsistency on the efficiency of the preconditioners. In some problems the coarse grid is not able to model small nonhomogeneous details and subproblems are material inconsistent. If we use for solving such problems the FAC–like techniques, the algorithm converges for suitable damping (see [1]). But if we use these techniques as preconditioners this material inconsistency can cause non-efficiency of these preconditioners. We tested the influence of material inconsistency on Benchmark I for three cases which differ by the value of Young modulus for the pillar in the coarse and fine grids: A0: E=31500 MPa for the coarse g., E=31500 MPa for the fine g. (mat. consist.) A1: E=1000 MPa for the coarse grid, E=31500 MPa for the fine grid A2: E=1 MPa for the coarse grid, E=31500 MPa for the fine grid. The results are shown in Table 2. The tests confirmed that strong material inconsistency can degrade the convergence of CG method with such a “preconditioner”. The reason is that the solution on a coarse grid gives in the case of
92
Roman Kohut
material inconsistency incorrect Dirichlet boundary conditions for the solution on a fine grid and a preconditioning provides pseudoresidual which does not correspond to the composite problem error. Tests show that in the case of strong inconsistency we must use the preconditioner 2 - the symmetric FAC method starting on a fine grid and we must solve subproblems more accurately. c) CPU time for various parts of the algorithm We solved Benchmark II with the sequential and parallel solvers to show how much time consuming various parts of the algorithm are when using the sequential solver and how it can be improved using the parallel solver. The results are shown in Table 3. Note that the parallel an sequential codes run on different computers. We see that the most time consuming part of the sequential code is the solution of linear systems for the subproblems. Further CPU time reduction will be possible after introducing a parallel access to the composite matrix–vector multiplication.
References 1. Blaheta, R.;Byczanski, P.; Kohut, R.: Composite grid finite element method: Implementation and iterative solution with inexact subproblems, Applications of Mathematics 47(2002),83–100 2. Kohut, R.: The FE on composite grids. The numerical tests, proceedings of the conference Contemporary mathematical methods in engineering, J. Doležalová, ed. TU Ostrava, 2002, pp. 99–104. 3. McCormick, S. F.: Fast adaptive grid (FAC) methods: theory for variational case, in Defect Correction Methods: Theory and Applications, K. Böhmer and H.J. Stebter, eds. Computing Supplementum, 5, Springer–Verlag, Wien, 1984, pp. 115–122. 4. Mathematical theory of elastic and elasto–plastic bodies: An introduction, Elsevier, Amsterdam 1981
Parallel Preconditioning for Sedimentary Basin Simulations Roland Masson1, Philippe Quandalle1, Stéphane Requena1, and Robert Scheichl2 1
2
Institut Français du Pétrole, Rueil-Malmaison, France
[email protected] Deptartment of Mathematical Sciences, University of Bath, UK
[email protected]
Abstract. The simulation of sedimentary basins aims at reconstructing its historical evolution in order to provide quantitative predictions about phenomena leading to hydrocarbon accumulations. The kernel of this simulation is the numerical solution of a complex system of non-linear partial differential equations (PDE) of mixed parabolic-hyperbolic type in 3D. A discretisation and linearisation of this system leads to very large, ill-conditioned, non-symmetric systems of linear equations with three unknowns per mesh cell, i.e. pressure, geostatic load, and oil saturation. This article describes the parallel version of a preconditioner for these systems, presented in its sequential form in [7]. It consists of three steps: in the first step a local decoupling of the pressure and saturation unknowns aims at concentrating in the “pressure block” the elliptic part of the system which is then, in the second step, preconditioned by AMG. The third step finally consists in recoupling the equations. Each step is efficiently parallelised using a partitioning of the domain into vertical layers along the and a distributed memory model within the PETSc library (Argonne National Laboratory, IL). The main new ingredient in the parallel version is a parallel AMG preconditioner for the pressure block, for which we use the BoomerAMG implementation in the hypre library [4]. Numerical results on real case studies, exhibit (i) a significant reduction of CPU times, up to a factor 5 with respect to a block Jacobi preconditioner with an ILU(0) factorisation of each block, (ii) robustness with respect to heterogeneities, anisotropies and high migration ratios, and (iii) a speedup of up to 4 on 8 processors.
1 Introduction In recent years the 3D modelling and simulation of sedimentary basins has become an integral part in the exploration of present and future reservoirs for almost all major oil companies. It aims at reconstructing the historical evolution of a sedimentary basin in order to provide quantitative predictions about phenomena leading to hydrocarbon accumulations. A simplified kinematic model of the geometry of the basin is first computed from the geology of the basin using a back-stripping algorithm. The full model I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 93–102, 2004. © Springer-Verlag Berlin Heidelberg 2004
94
Roland Masson et al.
comprising hydrocarbon generation, heat transfer, compaction of the porous media, and multi-phase Darcy flow is then calculated forward in time adding layer after layer using the geometric history calculated during the back-stripping process. The most computing intensive part of the simulation consists in solving numerically a complex system of non-linear partial differential equations (PDEs) modelling the compaction of the porous media and multi-phase Darcy flow in 3D. These equations are discretized using a cell-centred finite volume method in space and an implicit Euler scheme in time, and linearised using Newton’s method. In the case of two-phase flow (water – oil), we will therefore have to solve at each time step and in each Newton iteration, a system of coupled linear equations with three unknowns per element (pressure, geostatic load, oil saturation), very large, non-symmetric, and ill-conditioned, in particular due to the strong heterogeneities and anisotropies of the porous media. The idea for our preconditioning strategy is based on the methods developed in [2,3,5,9] for the related problem of oil reservoir simulation and is described in detail in [7]. It consists of three steps. First of all the equations for pressure and saturation are locally decoupled by taking linear combinations of the two equations on each element. This decoupling aims not only at reducing the coupling, but also at concentrating in the pressure block the elliptic part of the system which requires a good global preconditioning. The second step consists then in preconditioning the pressure block by an algebraic multi-grid method. The recoupling of the pressure with the other unknowns is then in a final step achieved by applying a block Gauss-Seidel strategy or the combinative technique defined in [2] for the reservoir case. Each step of the preconditioner is efficiently parallelised using a partitioning of the domain into vertical layers along the and a distributed memory model within the PETSc library (Argonne National Laboratory, IL). Only slight modifications are necessary for most of the components of the sequential preconditioner in [7]. The main new ingredient which is necessary however, is a parallel preconditioner for the pressure block for which we use BoomerAMG [4] from the hypre package (Lawrence Livermore National Laboratory, CA). We present results with the sequential preconditioner for a new test case with very high migration ratios which was not available for [7]. For this test case, the Quasi-IMPES decoupling together with a recoupling using the combinative technique outperforms all other combinations suggested in [7] significantly. This suggests that in the case of high migration ratios a local decoupling of the two mass conservation equations does not reduce the global coupling of these two equations significantly. Moreover, Gauss decoupling and Householder decoupling destroy the ellipticity of the pressure block and thus AMG does not work very well anymore. All the performance tests (sequential and parallel) were therefore carried out with Quasi-IMPES decoupling. In a series of numerical tests, the performance of the preconditioner is compared to block Jacobi with an incomplete LU factorisation, ILU(0), of each block, previously the only way to precondition these linear systems efficiently in paral-
Parallel Preconditioning for Sedimentary Basin Simulations
95
lel. We observe a very significant reduction of the CPU-time for the linear solver on one processor, up to a factor 5 with respect to ILU(0). The performance of the preconditioner shows no degradation with respect to the number of elements or to strong heterogeneities and anisotropies in the porous media, and depends only very mildly on the migration ratios of oil. Furthermore, the parallel solver exhibits good speedup on an SGI Origin2000. In all the test cases we obtain speedups between 3 and 4. The paper is organised as follows. In Section 2 we will give a detailed description of the preconditioning strategy, followed by a series of numerical tests in Section 3.
2
Preconditioning Strategy
The mathematical model for the forward problem is formulated as a system of 4 coupled non-linear PDEs and accounts for the conservation equations of two phase Darcy flow (water and oil), as well as the conservation equation of vertical momentum describing the compaction of the porous media together with a rheology law relating the porosity to the geostatic load and to the average fluid pressure. We refer to [7] and [8] and to the references therein for a detailed description of the model. The equations are discretized using a finite volume scheme in space and a fully implicit time integration. After a Newton linearisation and an elimination of the rheology law we end up at each time step and in each Newton iteration with a system of linear equations of the form
where each one of the blocks in A is an N × N matrix with N being the number of mesh cells. The block rows correspond to the discretisations of the water conservation equation, the vertical compaction equation and the oil conservation equation, respectively. The block columns correspond to the derivatives with respect to the primary variables (i.e. average pore pressure, geostatic load and oil saturation), respectively. The details of the discretisation and the linearisation can be found in [7]. System (1) is very large, non-symmetric and ill-conditioned, in particular due to the strong heterogeneities and anisotropies of the porous media. For an efficient and robust iterative solution of this system, it is therefore crucial to find good preconditioners. The idea for our preconditioning strategy stems from the related field of oil reservoir simulation, and was first presented for sedimentary basin simulations in [7]. In reservoir simulations, the geological time spans that are simulated are much shorter in comparison to the time spans considered here (i.e. years instead of million years), so that the porosity and the effective stress can be kept constant, thus leading to systems similar to (1), but in pressure and
96
Roland Masson et al.
saturation only. In [2, 3, 5] a preconditioning strategy has been developed for these problems decoupling the treatment of pressure and saturation. In [7] we have used a similar strategy for (1) which consists of three steps: (i) local decoupling of the two mass conservation equations on each cell of the mesh (or in other words, choosing an appropriate equation for the average pore pressure in (ii) preconditioning of the pressure unknowns, (iii) preconditioning of the remaining unknowns (Block Gauss-Seidel), or if this is not sufficient, feedbackcoupling with the pressure equation (two-stage preconditioners). We will describe these three steps briefly and explain in particular how they are parallelised. In order to do this we need to first describe the parallelisation strategy.
2.1
Parallelisation Strategy
At the moment, the parallelisation uses a partitioning of the domain into vertical layers along the and a distributed memory model. However, this onedimensional topology for the parallel model is inherited from the parallelisation of the entire sedimentary basin simulation code and the preconditioner itself is not restricted to a partitioning into vertical layers. Communications between the processors and synchronisation are handled using MPI (Message Passing Interface) within the PETSc library (Argonne National Laboratory, IL) on the basis of a ghost point strategy (see [1] for details). The parallelisation of each individual component of the preconditioner presented in [7] is discussed in the following.
2.2
First Step: Local Decoupling – Choice of the Pressure Equation
The decoupling step corresponds to multiplying system (1) by
and leads to the transformed system
with of (1) by
and The matrix
This corresponds to a left preconditioning is chosen such that
(a) concentrates the elliptic part of the system, (b) the block (c) the norm of is O(1).
Parallel Preconditioning for Sedimentary Basin Simulations
97
In [7] we proposed three different choices for based on Gaussian elimination, on Householder reflection, and on a quasi-explicit treatment of the saturation (Quasi-IMPES), respectively. Unfortunately none of these choices satisfies all the three criteria above. The first choice satisfies (a), but does not necessarily satisfy (b) and (c) very well; the second choice satisfies (a) and (c), but again does not satisfy (b) very well; the third choice on the other hand does not satisfy (a), but satisfies (b) and (c). We will analyse the importance of these three criteria more carefully in Section 3.1. No additional work is necessary to parallelise this step, since all the operations are local to each mesh cell and thus local to each processor.
2.3
Second Step: Pressure Block Preconditioner
From the decoupling step, the block should concentrate the ellipticity, and thus the ill-conditioning of the system and basically correspond to a discrete diffusion operator with a strongly heterogeneous and anisotropic diffusivity tensor. We propose to use algebraic multi-grid (AMG) which is known to be efficient and robust for such stiff elliptic linear systems, even in the presence of strong heterogeneities and anisotropies. More precisely, we shall use BoomerAMG by Henson and Yang [4], a very efficient and robust parallel implementation of AMG within the hypre software package (Lawrence Livermore National Lab, CA). To test whether this implementation is competitive in the sequential case, we will also include some results in Section 3 comparing BoomerAMG on one processor with the implementation AMG1R5 by Ruge and Stüben [6] which was used in [7],
2.4
Third Step: Recoupling
The decoupling step is aimed at reducing the dependency of the pressure equations on the saturation. Thus, provided the decoupling is effective, we can assume that the block is small compared to Furthermore, physical considerations also allow us to make the same assumption about the block (see [7] for details). This leads to the idea for the following Block Gauss-Seidel (BGS) preconditioner for (3):
Here, is the AMG preconditioner for the pressure block discussed above, and is a preconditioner for the saturation block Since the dependency on saturation is hyperbolic or transport dominated parabolic, it is sufficient to use a simple relaxation scheme, like Jacobi or Gauss-Seidel, for In Section 3 we will use one iteration of a hybrid version of Jacobi and Gauss-Seidel for which involves no communication between the different processors and reduces to Gauss-Seidel on each processor. Finally, since the compaction equation is one dimensional and can be solved in each column independently, the block can
Roland Masson et al.
98
be cheaply inverted by back substitutions. This is also the case in the parallel version, provided each vertical mesh column is assigned to one processor. The assumption that the blocks and can be neglected may be too strong. It is necessary in such a case that the preconditioner also provides some feedback from the second and the third block row to the first. A way of providing such a feedback-coupling is to combine the Block Gauss-Seidel preconditioner in a multiplicative way with a second preconditioner that provides (at least locally) such a coupling and that is cheap to invert. A good candidate for such a preconditioner is zero fill-in incomplete LU factorisation, ILU(0), of It is cheap and provides a good local coupling of the different physical unknowns. Again to reduce communication in the parallel version we carry out the incomplete LU factorisation only locally on each processor. In other words, the second preconditioner is chosen to be a block Jacobi preconditioner with an ILU(0) factorisation of each block, denoted The combined preconditioner can then be written as
Similar techniques in reservoir simulations, notably in [2] and [5], are usually referred to as combinative two-stage preconditioners (C2S) and we will adopt the same name. The recoupling preconditioners and are used as right preconditioners for (3). And so in summary (putting all three steps together) we obtain the following preconditioned system:
where
3
is either
and
is either
or
Numerical Results
In this section we will discuss the results of the numerical tests which we effectuated to evaluate the performance of the preconditioner in terms of efficiency and robustness on some test cases from real case studies. The five test cases are subsections of sedimentary basins taken from real case studies of major oil companies. These studies are confidential and so we will refer to the test cases as Problems A – E. Problems A and D are problems with strong heterogeneities and anisotropies in the permeability tensors of the porous media but with low migration ratios, and thus represent almost single-phase flow. Problems B and C are problems with higher migration ratios, but without any strong heterogeneities in the permeability tensors. Problem E, on the other hand, comprises both these difficulties and is thus the hardest test case (not yet available in [7]). We will only regard a set of time steps towards the end of the simulation, when most the are deposited and the linear systems are the largest. The number of unknowns ranges from 16974 for Problem A to 129756 for Problem E. Unfortunately, larger problems of entire sedimentary basins were not available for reasons of confidentiality.
Parallel Preconditioning for Sedimentary Basin Simulations
99
As the iterative solution method for the preconditioned systems (6) we use the Bi-CGStab method by Van der Vorst [10] which is particularly suited for nonsymmetric linear systems. The stopping criterion is the reduction of the residual by a factor of The CPU-times are those obtained on an SGI Origin2000 using between 1 and 8 processors. We will compare the results obtained with our preconditioner with the results using block Jacobi preconditioning with an incomplete LU factorisation ILU(0) of each block, previously the only way to precondition these linear systems efficiently in parallel.
As we can see in Table 1, the performance of ILU(0) deteriorates rather strongly as the mesh size gets larger even in the sequential case, in particular for problems with strong heterogeneities (i.e. A, D, and E). Moreover, the block Jacobi parallelisation of it provides no global preconditioning at all and will eventually be not sufficient anymore for convergence (when the number of processors gets too large). Increasing the fill-in for the incomplete LU decomposition does not cure these problems, and the reduction in the number of iterations is in all cases weighed off by the extra cost of each iteration in terms of efficiency.
3.1
Comparison of the Different Decoupling/Recoupling Strategies
To compare the robustness of the different decoupling and recoupling strategies which have been proposed in Section 2, we will look at the average number of BiCGStab iterations per Newton iteration in the sequential case. These are given Based on the results for Problems A – D, we concluded in [7] that the choice of decoupling has no strong influence on the robustness of the preconditioner, but that for problems with high migration ratios the block Gauss-Seidel recoupling was not sufficient to guarantee the robustness of the preconditioner anymore. The combinative two-stage preconditioner, on the other hand, proved to be very robust in all cases. The new test case E however, which combines both strong heterogeneities and high migration ratios, gives us some very valuable new insight into the robustness of our preconditioner. In particular, we can observe that Gauss decoupling, (as well as Householder decoupling lead to a much worse
100
Roland Masson et al.
performance than Quasi-IMPES decoupling i.e. 55.4 iterations for in comparison to 8.4 iterations for using two-stage recoupling. This is probably due to the loss of ellipticity in the pressure block. The results also underline (even more dramatically) that block Gauss-Seidel recoupling is not sufficient for problems with high migration ratios, i.e. 88.7 iterations for block Gauss-Seidel in comparison to 8.4 iterations for the two-stage recoupling (using Thus, we can conclude that in the case of high migration ratios a local decoupling of the two mass conservation equations does not reduce the global coupling of the two equations significantly. However, the combinative two-stage preconditioner provides the necessary recoupling and is very robust in combination with Quasi-IMPES decoupling (see the final column in Table 1).
3.2
Comparison of the Pressure Preconditioners
In order to allow for a parallelisation of AMG the BoomerAMG implementation by Henson and Yang [4] differs from the original AMG code AMG1R5 [6] in its coarsening strategy. (Here we use Falgout coarsening within BoomerAMG.) To test whether BoomerAMG is competitive as the pressure preconditioner in the sequential case, we compare in Table 2 the results for Problems D and E using one V-cycle of BoomerAMG on one processor with the results using one V-cycle of AMG1R5 [6]. We see that apart form slight variations they perform almost identically.
We also include (in Table 2) the number of iterations for our preconditioner when the pressure block is inverted exactly using an LU factorisation of The number of iterations decreases at most by a factor of 2 which is astonishing.
3.3
Comparison with Block Jacobi – Parallel Speedup
Finally and most importantly we look at the parallel robustness and efficiency of our preconditioner and compare it to block Jacobi preconditioning with ILU(0) per block, The results (with Quasi-IMPES decoupling) for Problems D and E are given in Tables 3 and 4, respectively. First of all, observe the extremely good parallel robustness of our preconditioner for all of the recoupling strategies. The number of iterations hardly grows at all with the number of processors. In terms of CPU-time, our preconditioner
Parallel Preconditioning for Sedimentary Basin Simulations
101
Fig. 1. Parallel Speedup: Problems D (left) and E (right)
is more than 3 times more efficient than on one processor and the parallel speedup is very good: between 3 and 4 on 8 processors (see Figure 1). This is in fact about the same speedup than the one reported in [4] for BoomerAMG on more simple test problems. Finally, it is interesting to note that the modification of the combinative two-stage recoupling seems to lead to a better efficiency of the preconditioner both in terms of iterations and CPU-time and that this method therefore is our method of choice.
102
Roland Masson et al.
References 1. S. Balay, W. Gropp, L.C. McInnes, and B. Smith, PETSc Users Manual, Technical Report ANL-95/11 – Revision 2.1.0, Argonne, IL (2001). 2. A. Behie and P.K.W. Vinsome, Block iterative methods for fully implicit reservoir simulation, Soc. Petroleum Eng. J 22 (1982), 658–668. 3. H.C. Edwards, A parallel multilevel-preconditioned GMRES solver for multiphase flow models in the Implicit Parallel Accurate Reservoir Simulator (IPARS), TICAM Report 98-04, The University of Texas at Austin (1998). 4. V.E. Henson and U.M. Yang, BoomerAMG: A parallel algebraic multigrid solver and preconditioner, Applied Numerical Mathematics 41 (2002), 155–177. 5. S. Lacroix, Y.V. Vassilevski, and M.F. Wheeler, Decoupling preconditioners in the Implicit Parallel Accurate Reservoir Simulator (IPARS), Numer. Lin. Alg. Appl. 8 (2001), 537–549. 6. J.W. Ruge and K. Stüben, Algebraic Multigrid (AMG), In Multigrid Methods (S.F. McCormick, ed.), Frontiers in Applied Mathematics, vol. 5, SIAM, Philadelphia, 1986. 7. R. Scheichl, R. Masson, and J. Wendebourg, Decoupling and block preconditioning for sedimentary basin simulations in TEMIS3D, submitted to Computational Geosciences, Bath Mathematics Preprint 02/05, University of Bath (2002). 8. F. Schneider, S. Wolf, I. Faille, and D. Pot, A 3D basin model for hydrocarbon potential evaluation: Application to Congo Offshore, Oil and Gas Science and Technology - Rev. IFP 55, 1 (2000), 3–13. 9. Y.V. Vassilevski, Iterative Solvers for the Implicit Parallel Accurate Reservoir Simulator (IPARS), II: Parallelization Issues, TICAM Report 00-33, The University of Texas at Austin (2000). 10. H.A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Comput. 12 (1992), 631–644.
Part III
Monte Carlo and Quasi-Monte Carlo Methods
This page intentionally left blank
Modeling of Narrow-Width SOI Devices: The Role of Quantum Mechanical Narrow Channel Effects on Device Performance Shaikh S. Ahmed and Dragica Vasileska Department of Electrical Engineering and Center for Solid State Electronics Research Arizona State University, Box 875706, Tempe, AZ 85287-5706, USA {shaikh.ahmed,vasileska}@asu.edu
Abstract. The impact of quantum mechanical space-quantization effects on the operation of a narrow-width SOI device structure has been investigated. The presence of a two-dimensional carrier confinement (both vertical and along the width direction) gives rise to larger average displacement of the carriers from the interface and lower sheet electron density in the channel region. This, in turn, results not only in a significant increase in the threshold voltage but also in pronounced channel width dependency of the drain current. In these simulations we have used classical 3D Monte Carlo particle-based simulations. Quantum mechanical space-quantization effects have been accounted for via an effective potential scheme that has been quite successful in describing bandgap widening effect and charge set back from the interface in conventional MOSFET devices.
1 Introduction For quite some time, the dimensions of semiconductor devices have been scaled aggressively in order to meet the demands of reduced cost per function on a chip used in modern integrated circuits. There are some problems associated with device scaling, however. Critical dimensions, such as transistor gate length and oxide thickness, are reaching physical limitations. Considering the manufacturing issues, photolithography becomes difficult as the feature sizes approach the wavelength of ultraviolet light. In addition, it is difficult to control the oxide thickness when the oxide is made up of just a few monolayers. In addition to the processing issues, there are also some fundamental device issues. As the oxide thickness becomes very thin, the gate leakage current due to tunneling increases drastically. This significantly affects the power requirements of the chip and the oxide reliability. Short-channel effects (SCEs), such as drain-induced barrier lowering (DIBL) and the Early effect in bipolar junction transistors (BJTs), degrade the device performance. Hot carriers also degrade device reliability. The control of the density and location of the dopant atoms in the MOSFET channel and source/drain region to provide a high on-off-current ratio becomes a problem in the 50 nm node devices where there are no more than 100 impurity atoms in the device active region. Yet another issue that becomes prominent in nano-scale I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 105–111, 2004. © Springer-Verlag Berlin Heidelberg 2004
106
Shaikh S. Ahmed and Dragica Vasileska
MOSFET devices is the quantum-mechanical nature of the charge description which, in turn, gives rise to inversion layer capacitance comparable to the oxide capacitance. This, in turn, degrades the total gate capacitance and, therefore, the device transconductance. A solution to some of the above mentioned problem, in order to achieving enhanced device performance, is to use silicon-on-insulator (SOI) materials. Over the last three decades, SOI CMOS has been identified as one possible method for increasing the performance of CMOS over that offered by simple scaling. However, prior to 1990’s, SOI had not been suitable as a substrate for mainstream applications. The barriers to its widespread usage were many, the main ones being SOI material quality, device design, and the steady progress in bulk CMOS performance through scaling. In view of these problems, IBM launched the first fully functional SOI mainstream microprocessor in 1999 marking that SOI technology was becoming the state-of the art technology for future lowpower ICs. An SOI SIMOX (separation by implanted oxygen) substrate with partially depleted epitaxial films (greater than 0.15 micron) was used for this purpose following a 0.22-micron technology. With this effort, the IBM specifications predict a 25 – 35% improvement over bulk CMOS counterpart, which is equivalent to about two years of progress in bulk CMOS design and fabrication process [14]. The above described SOI devices are not without problems, however. The thin gate oxide gives rise to gate leakage and the quantum-mechanical charge description due to the vertical confinement leads to device transconductance degradation. The quantization of the channel in the FD device along the growth direction gives rise to threshold voltage increase. This is a consequence of the fact that there is a reduction in the sheet electron density due to the smaller density of states function of the quasi-two-dimensional electron gas (Q2DEG) and the vanishing of the wavefunctions at the interface because of the large potential barriers (3.24eV). In a recent work by Majima et al. [13], it has been shown that, if the channel width is on the order of 10 nm or so, quantization occurs in the lateral direction as well. Even though this device structure has top oxide thickness of 34 nm, it serves as a proof of concept that a two-dimensional quantization effects can give rise to significant threshold voltage shift in nanoscale SOI device structures. It is the purpose of this paper to investigate the observed threshold voltage shifts in the device structure fabricated by Majima et al. [13] due to quantum-mechanical space-quantization effects using the effective potential scheme proposed by Ferry et al. [1]. It is worth noting that in some previous investigations we have shown that the effective potential approach can be successfully used for the case of two-dimensional carrier confinement effects in a narrow width wires, and the simulation results for the line electron density obtained by using the effective potential approach and the self-consistent solution of the 2D Schrödinger-Poisson problem can be found in [1]. The incorporation of the effective potential approach into a Monte Carlo particle-based simulator allows us, for the first time, to investigate the device transfer and output characteristics with proper treatment of two-dimensional quantization
Modeling of Narrow-Width SOI Devices
107
effects, velocity overshoot and carrier heating on an equal footing. Previously, this scheme has been applied to a conventional MOSFET device structure in which only one-dimensional quantum-mechanical size-quantization effects have been considered [7].
2
Theoretical Model
The inclusion of quantum effects in the description of the inversion layer at the semi-conductor/oxide interface of a SOI device involves solving the Schrödinger equation for the carriers in an approximately rectangular potential well. As a result, one obtains bound states, which give rise to two major features: reduced sheet density and charge set-back. Since the lowest bound state can be regarded as the new bottom of the conduction band, the spacing between the Fermi level and the conduction band edge is effectively increased, which results in the reduced sheet charge density with respect to the case in which quantum effects are excluded. Moreover, the probability density in the lowest bound state now has a maximum away from the top semiconductor/oxide interface, resulting in charge displacement from the oxide, which accounts for an effective increase in the oxide thickness. An alternative to solving the Schrödinger wave equation is to use quantum potentials. The idea of quantum potentials originates from the hydrodynamic formulation of quantum mechanics, first introduced by de Broglie and Madelung [4,5,12], and later developed by Bohm [2,3]. In this picture, the wave function is written in complex form in terms of its amplitude and phase. When substituted back into the Schrödinger equation one arrives at coupled equations of motion for the density and phase. The equations arising from this so-called Madelung transformation to the Schrödinger equation have the form of classical hydrodynamic equations with the addition of an extra potential, often referred to as the quantum or Bohm potential. The Bohm potential essentially represents a field through which the particle interacts with itself. It has been used, for example, in the study of wave packet tunneling through barriers [6], where the effect of the quantum potential is shown to lower or smoothen barriers, and hence allow for the particles to leak through. In analogy to the smoothed potential representation discussed above, Ferry et al. [7] suggested an effective potential that emerges from a wave packet description of particle motion, where the extent of the wave packet spread is obtained from the range of wavevectors in the thermal-distribution function (characterized by an electron temperature). The effective potential, is related to the self-consistent Hartree potential, V, obtained from the Poisson equation, through an integral smoothing relation
where G is a Gaussian with the standard deviation The effective potential is then used to calculate the electric field that accelerates the carriers in the transport kernel of the simulator described below.
108
Shaikh S. Ahmed and Dragica Vasileska
Regarding the Monte Carlo model, used in the transport portion of the simulator, it is based on the usual Si band-structure for three-dimensional electrons in a set of non-parabolic with energy-dependent effective masses. The six conduction band valleys are included through three pairs: valley pair 1 pointing in the (100) direction, valley pair 2 in the (010) direction, and valley pair 3 in the (001) direction. The explicit inclusion of the longitudinal and transverse masses is important and this is done in the program using the Herring-Vogt transformation [9]. Intravalley scattering is limited to acoustic phonons. For the intervalley scattering, we include both and processes. At present, impact ionization, surface-roughness and Coulomb scattering are not included in the model. They are omitted as they tend to mask the role of the space-quantization effects on the overall device performance. In solving Poisson’s equation, the Monte Carlo simulation is used to obtain the charge distribution in the device. We use the Incomplete Lower-Upper decomposition method for the solution of the 3D Poisson equation. After solving for the potential, the electric fields are calculated and used in the free-flight portion of the Monte Carlo transport kernel. However, the charges obtained from the EMC simulation are usually distributed within the continuous mesh cell instead of on the discrete grid points. The particle mesh method (PM) is used to perform the switch between the continuum in a cell and discrete grid points at the corners of the cell. The charge assignment to each mesh-point depends on the particular scheme that is used. A proper scheme must ensure proper coupling between the charged particles and the Coulomb forces acting on the particles. Therefore, the charge assignment scheme must maintain zero self-forces and a good spatial accuracy of the forces. To achieve this, two major methods have been implemented in the present version of the code: the Nearest-Grid-Point (NGP) scheme and the Cloud-in-Cell (CIC) scheme. The cloud-in-cell scheme (CIC) produces a smoother force interpolation, but introduces self-forces on non-uniform meshes. These issues have been dealt with extensively by Hockney and Eastwood [10], and quite recently by Laux [11]. Note that the electric field used in the free-flight portion of the simulator is calculated using the effective potential approach due to Ferry. Because of the presence of the semiconductor-oxide barrier, the convolution of the Hartree potential, obtained from solving the Poisson equation, and a Gaussian function with smoothing parameter of 0.63nm along the growth direction and 1nm along the channel (from source to drain) gives rise to electric fields that repel the carriers in the vicinity of the top semiconductor/oxide interface. This gives rise to larger average displacement of the carriers from the interface and degradation of the total gate capacitance due to the increase of the effective oxide thickness.
3
Simulation Results
The device structure we simulate consists of a thick silicon substrate, on top of which is grown 400nm of buried oxide. The thickness of the silicon on insulator layer is 7nm, with width of 10nm. The channel length is 50nm and the
Modeling of Narrow-Width SOI Devices
109
doping of the is On top of the SOI layer sits a gate-oxide layer, the thickness of which is 34nm. This is a rather thick gate oxide, but we have used it to compare our simulation results with the experimental data of Majima et al. [13]. The doping of the source/drain junctions equals and the gate is assumed to be a metal gate with workfunction equal to the semiconductor affinity.
Fig. 1. Width dependence of the threshold voltage for
The use of the effective potential shifts the conduction band edge upwards along the width and the depth of the device. It, therefore, accounts for the socalled band-gap widening effect, which leads to a reduction of the carrier density at the interface. Also, the electrons are moved away from the interface because of the additional perpendicular electric field in the vicinity of the interface. The quantization of charge in the inversion layer produces an expected increase in the threshold voltage of the device. The increase in the threshold voltage in the structure being investigated is due to both lateral and vertical confinement. The width dependence of the threshold voltage is shown in Figure 1. The sharp decrease in the threshold voltage with increasing channel width can be explained by increase in the channel conductance due to less quantized carriers. Note that similar trends have been observed in the experimental device structure from [13]. The slight discrepancy between the theory and the experiment can be due to two factors. First, the experimental device is grown on a (110) substrate and the theory is performed for a (100) substrates. Second, the threshold voltage in [13] is extracted using the constant current technique, whereas we have used the normalized mutual integral difference method due to He and coworkers [8]. The normalized mutual integral difference method utilizes the exponential-linear characteristic of the drain current versus gate voltage to obtain the drain voltage. As such, it is much better than any of the conventionally used methods including constant current technique, the linear extrapolation technique, the second derivative technique, the quasi-constant current technique, etc.
110
4
Shaikh S. Ahmed and Dragica Vasileska
Conclusions
In this work, we have utilized the effective potential approach to successfully simulate two dimensional space quantization effects in a model of a narrowchannel SOI device structure. The effective potential provides a set back of the charge from the interface, and a quantization of the energy within the channel. Both of these effects lead to an increase in the threshold voltage. We find a threshold voltage shift of about 250mV when the effective potential is included in the model for a device with 10nm channel width. Note that all simulations have been performed on a dual processor PC using Fortran 90. Also note that the scheme proposed by Ferry for incorporation of the quantum-mechanical spacequantization effects leads to only 10% increase of the overall CPU time. The solution of the 2D Schrödinger equation along slices of the device would be much more computationally costly.
Acknowledgements The authors would like to thank Prof. Stephen M. Goodnick, and D. K. Ferry for valuable discussions during the preparation of this manuscript. The financial support from the Office of Naval Research under Contract No. N000149910318 and the National Science Foundation under Contract Nos. NSF-ECS-9976484 and NSF-ECS-0214867 are also acknowledged.
References 1. R. Akis, S. Milicic, D. K. Ferry, and D. Vasileska, An effective potential method for including quantum effects into the simulation of ultra-short and ultra-narrow channel MOSFETs, Proceedings of the 4th International Conference on Modeling and Simulation of Microsystems, Hilton Head Island, SC, March 19-21, (2001) 550–3. 2. D. Bohm, A suggested interpretation of the quantum theory in terms of hidden variables. I., Phys. Rev. 85 (1952) 166. 3. D. Bohm, A suggested interpretation of the quantum theory in terms of hidden variables. II, Phys. Rev. 85 (1952) 180. 4. L. de Broglie, Sur la possibilité de relier les phénomènes d’interference et de diffraction a la théorie des quanta de luminère, C. R. Acad. Sci. Paris 183 (1926) 447. 5. L. de Broglie, La structure atomique de la matière et du rayonnement et la Mècanique ondulatoire, C. R. Acad. Sci. Paris 184 (1927) 273. 6. C. Dewdney and B. J. Hiley, A quantum potential description of one-dimensional time-dependent scattering from square barriers and square wells, Found. Phys. 12 (1982) 27. 7. D. K. Ferry, R. Akis, and D. Vasileska, Quantum Effects in MOSFETs: Use of an Effective Potential in 3D Monte Carlo Simulation of Ultra-Short Channel Devices, IEDM Tech. Dig. (IEEE Press, New York, 2000) 287–290. 8. J. He, X. Xi, M. Chan, K. Cao, C. Hu, Y. Li, X. Zhang, R. Huang and Y. Wang, Normalized mutual integral difference method to extract threshold voltage of MOSFETs, IEEE Electron Dev. Lett. 23 (2002) 428–430.
Modeling of Narrow-Width SOI Devices
111
9. C. Herring and E. Vogt, Transport and Deformation-Potential Theory for ManyValley Semiconductors with Anisotropic Scattering, Phys. Rev. 101 (1956) 944. 10. R. W. Hockney and J. W. Eastwood, Computer Simulation Using Particles, (Maidenhead: McGraw-Hill, 1981). 11. S. E. Laux, On particle-mesh coupling in Monte Carlo semiconductor device simultion, IEEE Trans. CAD Integr. Circ. Syst. 15 (1996) 1266. 12. E. Madelung, Quantatheorie in hydrodynamischer form, Z. Phys. 40 (1926) 322. 13. H. Majima, H. Ishikuro, and T. Hiramoto, Experimental evidence for quantum mechanical narrow channel effect in ultra-narrow MOSFET’ s, IEEE Electron Dev. Lett. 21 (2000) 396. 14. G. G. Shahidi, SOI Technology for the GHz era, IBM J. Res. & Dev. 46 (2002) 121.
Monte Carlo Algorithm for Ballistic Object Tracking with Uncertain Drag Parameter* Donka Angelova1, Iliyana Simeonova2, and Tzvetan Semerdjiev1 1
Central Laboratory for Parallel Processing, Bulgarian Academy of Sciences 25A Acad. G. Bonchev, 1113 Sofia, Bulgaria
[email protected] 2 Center for Systems Engineering and Applied Mechanics (CESAME) Batiment Euler, 4, Avenue G. Lemaitre, B-1348 LOUVAIN-LA-NEUVE, Belgium
[email protected]
Abstract. The problem of tracking a reentry ballistic object by processing radar measurements is considered in the paper. Sequential Monte Carlo-based filter is proposed for dealing with high nonlinearity of the object dynamics. A multiple model configuration is incorporated into the algorithm for overcoming the uncertainty about the object ballistic characteristics. The performance of the suggested multiple model particle filter (PF) is evaluated by Monte Carlo simulation.
1 Introduction The flight of a ballistic object (BO) consists of three phases: boost, ballistic (free flight) and terminal (reentry) phase. The topic of investigation in the present paper is the object reentry trajectory, when the Earth’s atmosphere is reached and the atmospheric drag becomes considerable. This phase finishes with the landing point on Earth [11]. The precise estimation of BO motion parameters and the accurate prediction of its impact point are of great importance for defense and for safety against reentry of old satellites and falling debris [6]. There exist a lot of extensive studies of BO tracking by processing radar measurements or using electro optical sensors. The challenges that must be overcome are connected primarily with high nonlinearity of the dynamic system, formed by BO and sensor. In addition, difficulties arise due to the uncertainty of the ballistic object parameters and noisy observations, received by the sensor. There are two major approaches to nonlinear recursive estimation of the object dynamics [13]. The nonlinear state and measurement equations in the first one are approximated by Taylor series expansions. The linearized (about the current state estimate) functions are applied directly to the linear Kalman filter to produce Extended Kalman filter (EKF). Various algorithms based on EKF for * Research Supported in part by Center of Excellence BIS21 grant ICA1-2000-70016, an European Community Marie Curie Fellowship and in the framework of the Control Training Site, and by Bulgarian Foundation for Scientific Investigations grants I-1202/02 and I-1205/02. I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 112–120, 2004. © Springer-Verlag Berlin Heidelberg 2004
Monte Carlo Algorithm for Ballistic Object Tracking
113
the reentry phase are proposed in the literature, resulting in different trade-offs between accuracy and computational costs. However, when the filtering problem is highly nonlinear, the local linearity assumption breaks down and the EKF may introduce large estimation errors. The second approach is based on the approximation of the underlying density functions of the state vector. Recursive algorithms on the densities can be derived from Bayes’formula. These densitybased algorithms are preferable in the cases of both nonlinear equations and non-Gaussian error terms. The unscented Kalman filter and PF belong to this class. The variants of these filters are suggested in [6] for the purposes of reentry vehicle tracking. BO uncertainty during the reentry phase is concentrated on the drag characteristics [11]. In general, the ballistic profile of the foreign vehicle under surveillance is not known and must be estimated for precise tracking. A natural technique is to include drag (or another suitable quantity) into the state vector as a state to be evaluated [3,4,7]. The authors of [12] adopt an uncertain interval for a key system parameter (the atmospheric density gradient). Then the entire tracking system is modeled as an interval nonlinear system and analyzed via an extended interval Kalman filter. A Monte Carlo filter is proposed in the work for BO radar tracking. Since BO dynamics are governed by a stochastic differential equation (SDE), the time evolution of the BO state probability density follows a Fokker-Plank equation (FPE). A numerical solution of SDE is realized in order to approximate the probability density of the predicted state. The objective is to refine the proposal distribution and consequently to improve the overall estimation accuracy. A multiple model approach is proposed also for identifying the unknown drag parameter (DP). It is assumed that the ballistic coefficient (the inverse of DP) belongs to a discrete set of possible values. The rest of the paper is organized as follows. The problem under consideration is set up in Section 2. Section 3 presents the features of BO SDE and its approximate solution. The suggested PF is described in Section 4. Computer simulation results are shown in Section 5, with conclusions given in Section 6.
2
Problem Formulation
BO and Sensor Models. The starting point for modeling time evolution of BO state is the Ito SDE [8,9]
where is an vector, f is an vector valued function, g is an matrix with the system noise covariance matrix and is a Wiener process. The function of tracking filter is to estimate at time given a set of measurements made at discrete times
114
Donka Angelova, Iliyana Simeonova, and Tzvetan Semerdjiev
The measurement model is given by the equation
where is a measurement vector, h is a measurement function and is a Gaussian white noise sequence with zero mean and covariance R. Density-based Filtering. The objective of density-based filtering methods is to construct the state posterior probability density function (PDF) based on all available information. According to the Bayesian philosophy, may be obtained recursively within the time interval in two stages – prediction and update [5]: Prediction. PDF evolution is connected directly with the Ito equation (1). It is given by the FPE [8]
where the initial condition is available from the previous time step It is assumed that the initial PDF is known. Information Update. When the measurement is realized:
arrives, the update stage
The normalizing constant in the denominator depends on the likelihood function determined by the parameters of the measurement model (2). The measurements are assumed conditionally independent in time. All information about the state contained in the measurements is captured in the conditional posterior PDF (4). An optimal (with respect to any criterion) estimate of the state and a measure of its accuracy can be obtained from [1,5]. In particular, the mean can be BO state estimate solving in this way the filtering problem. The recursive propagation (3) and (4) of the PDF is only a conceptual solution and can be implemented exactly for a restrictive set of cases [1]. Whereas the simulation-based methods offer efficient approximations to this optimal Bayesian solution. Multiple Model (MM) Approach. One of the problems connected with BO tracking is that the unknown DP reflects on the uncertainty about the state transition function in equation (1). However, in practice the drag values are positioned in an a priori known fixed interval. MM approach is a widely used methodology for overcoming this problem. It is assumed that the object state belongs to one of models corresponding to one of discrete values in the drag interval. The prior probability that is correct is assumed known and
Monte Carlo Algorithm for Ballistic Object Tracking
115
independent model-matched filters are run in parallel to produce model-conditioned state estimates Given the measurement data the posterior probability of model being correct can be calculated using Bayes’ formula [2]:
The output estimate is the weighted sum of the individual estimates (combined estimate) or the output from the “best” filter (with maximum posterior probability).
3
Numerical Solution of BO SDE
During the reentry phase, two significant forces act on the object [11]: the Earth’s gravity and the atmospheric drag. The drag force acts opposite to the velocity vector with an intensity, proportional to the air density and the square of the object speed The drag induced acceleration is given by [11]
where denotes the object altitude, and is the drag parameter, depending on object mass, body shape, cross-sectional object area perpendicular to the velocity, Mach number, drag coefficient and other unknown parameters. Therefore, for the reentry tracking, all uncertainties associated with the drag are collected in the DP [11]. The air density is usually approximated as a locally exponential function of the object altitude where and are known constants for a particular layer of the atmosphere. In the simulation below are accepted the following constant values for and for according to [6]. Assuming a flat, nonrotating Earth model, BO motion model has the following state-space form in the sensor East-North-Up coordinate system:
where is the gravity acceleration and is the process noise intensity. In the terminology of SDE (1), the state vector includes BO positions and velocities in the radar-centered Cartesian coordinate system; f(x) and g(x) have the following form:
116
Donka Angelova, Iliyana Simeonova, and Tzvetan Semerdjiev
Euler approximation is used to generate approximate sample paths of a solution of BO SDE. For a given equidistant discretization of the time interval the Euler approximation realizes the following iterative scheme [10]:
where the components of are distributed increments of the standard Wiener process, L is some a priori chosen integer.
4
Simulation-Based Suboptimal MM Filter
The key idea of Monte Carlo methods is to represent the required posterior density functions by a set of random samples with associated weights and to compute estimates based on these samples and weights [5]. Respectively, the evolving PDFs in eqs. (3) and (4) are replaced by a set of random samples which are predicted and updated by the particle algorithm for independent PFs are run in parallel
bank of
where is the common number of particles. The weights of the particular filters are used to obtain model-conditioned estimates. The weights of all N particles take part in the calculation of the output combined estimate and posterior model probabilities. The algorithm is described as follows:
1. Initialization, k = 0. * For sample and set 2. For (possibly in parallel) execute * Prediction step for generate samples according to the Euler scheme. * Measurement processing step on receipt of a new measurement for evaluate the normalized weights
* Selection step resample with replacement from the set
particles according to the importance weights
Monte Carlo Algorithm for Ballistic Object Tracking
117
* Compute model-conditioned estimates
End for 3. Output: Compute combined output estimate and model posterior probabilities
4. Set
and go to step 2.
The suboptimality of the procedure is due to the finite number of samples used. As the sample size tends to infinity, the optimal results can be achieved.
5
Simulation Results
BO scenario. BO trajectories for two drag parameters are shown in Fig. 1. The true initial parameters
and
are chosen like [6]. Measurement model. Tracking radar usually provides measurements in a spherical coordinate system. The measurement vector comprising range and elevation measurements, has a nonlinear relationship with the object state variables. The form of the measurement function in eq. (2) is as follows: The error standard deviations of range and elevation angle measurements are and respectively. A measurement conversion is implemented from spherical to Cartesian coordinates: Thus the measurement function becomes linear. The components of the corresponding covariance matrix R are as follows [2]:
The time interval between measurements is Parameters of MM scheme. A bank of filters is implemented for DPs and identical with the scenario parameters. The prior probability of each model being correct is selected as The equal number of particles is chosen for each filter. Filter design parameters. The parameters of state vector initial distribution are selected as follows: contains the exact initial BO parameters and The following parameters of the Euler scheme are accepted: prediction integration step is L = 10; process noise variance: and The sample size is N = 10000. Measures of performance. The state estimation accuracy is evaluated in terms of mean absolute error (MAE) – the absolute value of the actual error, averaged over
118
Donka Angelova, Iliyana Simeonova, and Tzvetan Semerdjiev
runs. Position MAE (both coordinates combined) and speed (magnitude of the velocity vector) MAE are calculated in the simulation experiments. The average probability of correct model identification is a measure for correct recognition of the DP.
Fig. 1. BO Scenario: Trajectory (a)
Fig. 2. Position MAE (a)
and
and
(b) Speed versus time
(b) Speed MAE versus time
Simulation results. As it can be seen from Fig.1, trajectories with different drag parameters are close to each other in a rather long time interval. The differences become obvious after the 50-th scan, when the speeds rapidly distinguish one from the other. This fact complicates the task of tracking. The tracking filter performance is evaluated based on a trajectory with The results are obtained by averaging over 50 Monte Carlo runs. Position and speed MAEs of the combined estimate and the “best” filter (filter which parameter is tuned to estimate are shown in Fig.2. The “best” filter
Monte Carlo Algorithm for Ballistic Object Tracking
119
Fig. 3. Posterior model probabilities (a) and (b) PDF histograms
estimate is better during the transitional time interval of identifying DP (between 50-th and 70-th scans), which is due to the fairly large posterior probability of the “wrong” filter. The averaged (over the runs) error standard deviation of the measurements (also shown in Fig.2(a)) can serve as a quality measure of the accuracy, achieved by the filter. The curve of the position MAE is below in the whole tracking interval. Plots of the posterior model probabilities are given in Fig.3(a). As it can be seen the delay in correct model detection is no more than 15 or 20 scans. The DP identification is accomplished with a high degree of confidence. PDF histograms for are presented in Fig.3(b). The posterior PDF of the appropriate model is located above the true object position, while the PDF of the “wrong” model is far from the desired place, determined mainly from the solution of the SDE with
6
Conclusion
Monte Carlo-based filter is suggested in the paper for tracking a reentry ballistic object by a radar. The objective is to explore the capability of particle algorithms for precise and reliable estimation of such highly nonlinear systems. The feature of the proposed version is connected with the SDE, describing object dynamics. A numerical solution of SDE is realized in order to refine the probability density of the predicted state and consequently to improve the overall estimation accuracy. MM approach is applied also for identifying the unknown drag parameter. The filter performance is examined by simulation over a typical BO scenario. The results show a reliable tracking and correct drag parameter determination. It gives an alternative solution to the difficult and important problem of BO tracking.
120
Donka Angelova, Iliyana Simeonova, and Tzvetan Semerdjiev
References 1. Arulampalam, S., Maskell, S., Gordon, N., Clapp, T.: A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking. IEEE Trans. Signal Processing, Vol. 50 (2002) 174–188. 2. Bar-Shalom, Y., Li, X.R.: Multitarget–Multisensor Tracking: Principles and Techniques. YBS Publishing, (1995) 3. Cardillo, G., Mrstik, A., Plambeck, T.: A Track Filter for Reentry Objects with Uncertain Drag. IEEE Trans. AES Vol. 35 (1999) 394–409. 4. Costa, P.: Adaptive Model Architecture and Extended Kalman-Bucy Filters. IEEE Trans. AES Vol. 30 (1994) 525–533. 5. Doucet, A., de Frietas, N., Gordon, N. (eds.): Sequential Monte Carlo Methods in Practice. Statistics for Engineering and Information Science. Springer-Verlag, New York (2001) 6. Farina, A., Ristic, B., Benvenuti, D.: Tracking a Ballistic Target: Comparison of Several Nonlinear Filters. IEEE Trans. AES Vol. 38 (2002) 854–867. 7. Farina, A., Benvenuti, D., Ristic, B.: Estimation accuracy of a landing point of a ballistic target. Proc. FUSION 2002 Conf., Annapolis, USA, (2002) 2–9. 8. Jilkov, V., Semerdjiev, Tz., Angelova, D: Monte Carlo Filtering Algorithm for Nonlinear Stochastic Environmental Model. Recent Advances in Numerical Methods and Applications II. World Scientific, London (1998) 266–274. 9. Kastella, K.: Finite Difference Methods for Nonlinear Filtering and Automatic Target Recognition. In: Bar-Shalom, Y., Blair, W. (eds.): Multitargrt-Multisensor Tracking. Applications and Advances, Vol. 3. Artech House, Boston (2000) 233– 258. 10. Kloeden, P., Platen, E., Schurz, H.: Numerical Solution of SDE Through Computer Experiments. Springer-Verlag, New York (1994). 11. Li, X., Jilkov V.: A Survey of Maneuvering Target Tracking - Part II:Ballistic Target Models. Proc. SPIE Conf. Signal and Data Processing of Small Targets, Vol. 4473-63, San Diego, CA, USA (2001) 12. Siouris, G., Chen, G., Wang, J.: Tracking an Incoming Ballistic Missile Using an Extended Interval Kalman Filter. IEEE Trans. AES Vol. 33 (1997) 232–240. 13. Tanizaki, H.: Nonlinear Filters. Estimation and Applications. Springer-Verlag (1996)
Efficient CPU-Specific Algorithm for Generating the Generalized Faure Sequences* Emanouil I. Atanassov Central Laboratory for Parallel Processing, Bulgarian Academy of Sciences Acad. G. Bontchev, Bl. 25A, 1113 Sofia, Bulgaria
[email protected]
Abstract. The Faure sequences are a popular class of low-discrepancy sequences. Their generalized variants, with better equi-distribution properties, are extensively used in quasi-Monte Carlo methods, especially for very high dimensional problems. The task of generating these sequences can take substantial part of the overall CPU time of a quasiMonte Carlo computation. We present an efficient algorithm for generating these sequences, and demonstrate how it may be tuned to use the extended instruction sets, available on many modern CPUs, to reduce drastically the CPU-time, spent for generating these sequences.
1 Introduction 1.1
Ideas of Monte Carlo and Quasi-Monte Carlo Methods
The main idea in the Monte Carlo methods is to represent the unknown quantity, as the mathematical expectation of some random variable so that by averaging over N independent samples of one can obtain an estimate of Usually the random variable is expressed as a function of independent random variables, uniformly distributed in [0,1]. Thus the function is defined in the unit cube and the Monte Carlo algorithm for approximating can be thought of as an algorithm for approximate calculation of the integral
by means of the formula:
where the values are computed using a pseudo-random number generator. The integer becomes the constructive dimension of the Monte Carlo algorithm *
Supported by the project of European Commission - BIS 21 under contract ICA1CT-2000-70016 and by the Ministry of Education and Science of Bulgaria under contract NSF I-1201/02 and NSF MM-902/99.
I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 121–127, 2004. © Springer-Verlag Berlin Heidelberg 2004
122
Emanouil I. Atanassov
(see, e.g, [10], p. 254). Such an algorithm has an order of convergence of the probable error In order to obtain faster convergence for suitable classes of functions, the idea of the quasi-Monte Carlo methods is introduced. Instead of random numbers, one can use a deterministic uniformly distributed sequence so that the average is computed using the values of at the first N terms of the sequence The quality of distribution of the sequence is usually measured by its discrepancy (for a definition see, e.g., [5]). It is believed that the best order of the discrepancy of an infinite sequence is (see the results of W.M. Schmid [9], K.F. Roth [8], Baker [1]), which yields an asymptotic order of the integration error, better than that of Monte Carlo. Infinite sequences, which achieve such order of convergence to zero of the discrepancy, are called “low-discrepancy” sequences. Various theoretical and practical results show that even for vary large the low-discrepancy sequences may outperform Monte Carlo on classes of functions, important for the applications (see, e.g., the work of Paskov and Traub [7], and of A. Papageorgiou and J.Traub [6]). The question of finding the best low-discrepancy sequence remains unsolved. Many classes of low-discrepancy sequences are known, and for different problems different classes perform better. One important class of lowdiscrepancy sequences are the sequences introduced by Faure. The generalized Faure sequences, proposed by Tezuka [11–13] and sometimes called GFaure, are widely used in practice. The difference from point of view of generation algorithms between the general and the particular case is small, and we decided to deal only with the general case.
1.2
Definitions of the Faure and Generalized Faure Sequences
Tezuka [11–13] introduced a generalization of the Faure sequences, adding more degrees of freedom, which permit the construction of better distributed sequences. We use the following definition (Faure [4]): Definition 1. Let Let matrices, and let
be a fixed integer, greater than or equal to the dimension be given infinite non-singular lower triangular be the powers of the Pascal matrix, so that
The term of the expanding in
generalized Faure sequence number system:
and then setting
is obtained by
Efficient CPU-Specific Algorithm
123
where by mod we denote the remainder of modulo If the matrices are all equal to the identity matrix, we obtain the original Faure sequences. These sequences are of low-discrepancy, and moreover, they are the first class of sequences, for which an estimate of this kind was obtained (Faure [3]):
with a constant tending to zeros as tends to infinity. This result suggests that these sequences should be good for practical purposes, and in the area of financial mathematics they become very popular for estimating some very high-dimensional integrals. They are used for instance in the so-called FinDer program [2], which is polupar in Financial Mathematics. Various constructions for the matrices are known. We assume that they are given to us as input.
1.3
Importance of CPU-Specific Generation Algorithms
Because of their similarity from algorithmic point of view, the quasi-Monte Carlo and classical Monte Carlo methods compete directly both in terms of precision and speed of computation. The main difference in these setting is that in the case of classical Monte Carlo we use a pseudo-random number generator, and in quasi-Monte Carlo methods we need a suitable generator function for the chosen low-discrepancy sequence. Obviously, for some applications the function will be complicated and expensive to evaluate in terms of computational time, while for others the main part of the CPU time will be spent in the generation. In most quasi-Monte Carlo algorithms one can use almost any of the popular low-discrepancy sequences and compare the results, analogously to the situation in Monte Carlo, where one is advised to test different pseudo-random number generators. This suggests that it is preferable to have generation functions with similar calling conventions for every popular class of low-discrepancy sequences. However, we aim to develop the most efficient implementation possible for a given computer architecture. Since there is a certain degree of fine-grained parallelism in the operations, required for generating the terms of the sequence, an important speed-up can be obtained by using the special instructions for processing multi-media data, which are available on most modern CPU. In this paper we concentrate on the most popular such instruction sets. The MMX instruction set was the first extension to the 386 instruction set, introduced by Intel. It was later implemented on the newer AMD processors like Athlon and Duron, and therefore it can be considered as standard for the newer Pentium-compatible processors. The SSE1 and especially the SSE2 instruction set, introduced by Intel, are more powerful, but are available only on the newest processors. We show how our algorithm can be implemented using the MMX and the SSE2 instruction set. Since the Pentium and Athlon processors are very widespread at both workstations and clusters, the speed-up obtained by using our algorithm will be available to a large part of the scientific community. Writing a version of the generation code for another instruction set is just a matter of implementing some simple operations on large vectors of numbers.
124
2
Emanouil I. Atanassov
Description of the New Generation Algorithm
We developed our algorithm under the assumption, that the terms of the sequence need to be generated consecutively. In such case it is justified to have a preprocessing phase, so that each term of the sequence could be easily generated using the preprocessed data and some data from the previous invocation of the generation function. The data is organized so as to make maximal use of the extended instructions available, which means the array describe below should be at 8-byte aligned memory locations. At the preprocessing stage we perform the following operations:
1. Input the dimensionality, of the sequence, the prime number the coefficients of the matrices and the index of the first term to be generated, 2. Compute the coefficients of the matrices 3. Compute the “skewed” coefficients, by the formula
4. Compute the digits system. 5. Fill the table of relative positions:
of
in
positional number
6. Compute the table of partial sums, defined as follows:
Note that we need at most the first 64 rows and columns of the matrices and since we work in double precision. The partial sums are, in fact, the coordinates of the term of the sequence. Observe that all these steps have complexity comparable to that of step 2. When the generation function is invoked for generating the Nth term of the sequence, we first compute the digits of N + 1 and copy the partial sums to the buffer, supplied by the user, since they represent the Nth term of the sequence. Then we proceed in two possible ways, depending on the index, of the first least-significant non-zero digit of N. If we perform the following operations:
1. For add to the partial sum greater than 1, subtract 1 from it; add to every relative position 2. For greater than subtract from it.
and if the result is and if it becomes
Efficient CPU-Specific Algorithm
125
The key point in the algorithm is to perform these operations using the extended instruction sets available, without any conditional jumps, which would degrade the performance. This is explained in more detail in the next section. If we perform the following operations:
1. For to 0 with step –1, do the following: (a) For every set to and if it becomes greater than subtract from it. (b) For every store in Obviously, the probability that will be greater than 1 is and therefore the way we handle this second case is not as crucial for the performance of the algorithm as the case We can vectorize the operations, that are performed here, in a similar manner to the previous case, but in this case the speed-up is not as dramatic. In the next section we give more details about the generation code that we wrote based on this algorithm. Note that we do obtain the sequence in its natural order, without any Gray code reordering.
3
Implementation Details
As it can be seen from the description of the algorithm, the most crucial part in terms of CPU time is the way we handle the case when the index, N, of the term of the sequence, is not divisible by the prime That is why when we implement this algorithm on a given computer architecture, we need to write CPU-specific code only for this part, even though the case can be handled in a similar way. Since the operations that need to be vectorized are relatively simple, we successfully wrote variants of the generation code for the MMX and the SSE2 instruction sets. We always worked in double precision, but it should not be a problem to write faster single precision versions. Note that the MMX instruction set is less powerful and does not allow the floating point operations in double precision to be vectorized. Yet we obtained good speed-up, as it can be seen in Table 1.
The vectorization is straight-forward, basically equivalent to manual loopunrolling. The code is available under the GNU Public license at: http://parallel.bas.bg/~emanouil/sequences.html
126
Emanouil I. Atanassov
Here we only give the main idea. We wish to perform efficiently the operations, described above, without using conditional jumps, because they significantly degrade the performance. We use the fact, that if we need to compute the expression
we can use the formula
where the plus sign denotes integer or floating point summation, and by we denote a sequence of bits, with values equal to the value of the predicate and with width in bytes equal to the width of and in bytes. Since our predicates are of comparison type, they are vectorized naturally and efficiently. As an example, we show how step 1 of the algorithm in the case is vectorized using the MMX instruction set (only the innermost loop is shown):
4 Timing Results We present timing results, obtained by compiling our code with the gcc compiler. The non-standard instructions are coded using inline assembly statements. In our tests we measured the time, required for producing ten million terms of the sequence in various dimensions. The generation speed is measured in millions of coordinates, generated per one second. We observed that the generation speed falls somewhere between that obtained with our generators for the Sobol’ and
Efficient CPU-Specific Algorithm
127
Halton sequences, which are also available at the above web address. Note that an average pseudo-random number generator runs at speed of around 10 millions numbers per second, and therefore the use of low-discrepancy sequences offers significant performance advantage. We also show the generation time and speed for the portable version of our algorithm, which is not restricted to the x86 architecture, so that the significant speed-up, obtained trough vectorization, can be observed.
Conclusions and Directions for Future Work
5
With the new vectorized algorithm we are able to achieve significant speed-up with respect to regular C or FORTRAN code implementation. At the same time porting the algorithm to another architecture would require only trivial changes. Our plans are to implement generation codes for some other popular classes of low-discrepancy sequences under the same paradigm.
References 1. R. C. Baker. On Irregularities of Distribution II. J. London Math, Soc., 2(59)
(1999) 50–64.
2. The FinDer Program, http://www1.cs.columbia.edu/~ap/html/finder.html. 3. H. Faure. Discrépance de suites associées à un système de numération (en dimen-
sion
Acta. Arith., 41 (1982)
4. H. Faure. Monte-Carlo and quasi-Monte-Carlo methods for numerical integration,
5. 6. 7. 8. 9. 10. 11. 12. 13.
Combinatorial & computational mathematics, (Pohang, 2000) 1–12, World Sci. Publishing, River Edge, NJ, 2001. H. Niederreiter, L. Kuipers. Uniform Distribution of Sequences. John Wiley & sons, New York, 1974. A. Papageorgiou and J. Traub. Beating Monte Carlo. Risk, June (1996) 63-65. S. Paskov and J. Traub. Faster Valuation of Financial Derivatives. Journal of Portfolio Management, Vol. 22:1, (1995) 113–120. K. F. Roth. On Irregularities of Distribution. Mathematika, Vol 1 (1954) 73–79. W. M. Schmidt. Irregularities of Distribution VII. Acta Arith., Vol. 21 (1972) 45–50. I. M. Sobol. Monte Carlo Methods. Nauka, Moscow, 1973. S. Tezuka. Polynomial Arithmetic Analogue of Halton Sequences. TOMACS, 3:2, (1993) 99–107. S. Tezuka , T. Tokuyama. A Note on Polynomial Arithmetic Analogue of Halton Sequences. TOMACS, 4:3 (1994) 279–284. S. Tezuka. Uniform Random Numbers: Theory and Practice. Kluwer Academic Publishers, Dordrecht, (1995).
A New Quasi-Monte Carlo Algorithm for Numerical Integration of Smooth Functions Emanouil I. Atanassov, Ivan T. Dimov, and Mariya K. Durchova Central Laboratory for Parallel Processing, Bulgarian Academy of Sciences Acad. G. Bontchev, Bl. 25A, 1113 Sofia, Bulgaria
[email protected],
[email protected],
[email protected]
Abstract. Bachvalov proved that the optimal order of convergence of a Monte Carlo method for numerical integration of functions with bounded order derivatives is w h where i s the dimension. W e construct a new Monte Carlo algorithm with such rate of convergence, which adapts to the variations of the sub-integral function and gains substantially in accuracy, when a low-discrepancy sequence is used instead of pseudo-random numbers. Theoretical estimates of the worst-case error of the method are obtained. Experimental results, showing the excellent parallelization properties of the algorithm and its applicability to problems of moderately high dimension, are also presented.
1 Introduction The paper proposes new quasi-Monte Carlo algorithm for integrating smooth functions. We consider integration over the unit cube The class of functions under consideration is the following: Definition 1. For given integers and consists of all real functions defined in
exist for all
and the class such that all the derivatives
and there absolute values are bounded by M.
The results of Bachvalov [2,3] establish lower bounds on the integration error of both deterministic and stochastic or Monte Carlo methods. Various Monte Carlo methods for approximate integration of such functions with the optimal order of convergence are known (see, e.g. [1,5,10,20]). In this paper we investigate from theoretical and practical view point a quasi-Monte Carlo algorithm, based loosely on the same ideas. The idea of quasi-Monte Carlo algorithms is to replace the pseudo-random numbers, used in Monte Carlo, with a deterministic sequence of points, uniformly distributed in some high-dimensional unit cube The quality of distribution of these sequences is measured through I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 128–135, 2004. © Springer-Verlag Berlin Heidelberg 2004
A New Quasi-Monte Carlo Algorithm
129
their discrepancy. Infinite sequences with order of the discrepancy which is believed to be the optimal, are called low-discrepancy sequences. Note that in Monte Carlo methods one can frequently obtain a statistical error estimate along with the result, which is necessary in many areas. In quasi-Monte Carlo methods a similar error estimate of statistical nature can be obtained using the so-called scrambling of sequences, which is a way of adding some randomness to otherwise entirely deterministic sequences. The most popular quasi-Monte Carlo integration method is based on the simple formula:
where is a uniformly distributed sequence. For a good introduction in the theory of uniform distribution modulo 1 see, e.g., the books [9] and [7]. More complex methods are developed and tested by many authors (see, e.g., [18, 16]). A method, based on scrambled nets, can be seen in [12]. In quasi-Monte Carlo methods it is important to achieve low constructive dimensionality (for a definition, see [17], p. 255). Since the first few coordinates of a low-discrepancy sequence are better distributed, various ways to adjust the integration procedure to the properties of the integrand are proposed (see, e.g., the Brownian bridge construction in [4]). The performance of the quasi-Monte Carlo method depends on the quality of the distribution of the underlying low-discrepancy sequence. Various families of such sequences are known, and we tested some of the most popular ones in our algorithm. The algorithm is described in Sec. 2. Numerical results, showing the applicability of the method and its excellent parallelization properties, are given in Sec. 3.
2
Description of the Algorithm
Since we are going to describe our algorithm using the term pseudo-inverse matrix , we provide the following Definition 2. (see e.g. [11], p. 257) Let A be an real matrix with rank Suppose that is the SVD of A. Then the pseudo inverse matrix of A is defined as where
is referred to as the pseudo inverse of A. If Definition 3. Let be an integer, Let for some M. The
and let
then be fixed points in with
130
Emanouil I. Atanassov, Ivan T. Dimov, and Mariya K. Durchova
can be ordered lexicographically and there are exactly of them. Consider the matrix B with rows and columns, such that the column of B corresponds to the tuple and contains all the products
Suppose that and that B has rank pseudo-inverse of B. C has rows and polynomial is defined by
Let the matrix C be the columns. Now the interpolation
Observe that if the points are in general position, the matrix B has rank Since in our definition B has always full rank, the pseudo-inverse C is equal to The reason for using formulae with for numerical integration is that the coefficients of the matrix C are much smaller in this case. Of all the matrices satisfying BAB = B the pseudo-inverse is chosen because its Frobenius norm is the smallest. Now let us fix some integers and greater than 1 and consider functions defined over the unit cube We also fix the number and the points such that an interpolation formula as described in Definition 3 is defined. Observe that by integrating over we get a quadrature formula
where
Definition 4. Consider a rectangular area and an interpolation formula as in definition 3. Let T be a linear transformation such that For a given function consider the function such that The interpolation formula is defined by Now we define a Monte Carlo integration formula, which we are going to investigate in the sequel. Definition 5. Let be an integer. Consider a representation of the unit cube as a union of N rectangles
A New Quasi-Monte Carlo Algorithm
For the rectangle
131
we consider the simplest linear transfor-
mation T such that
By
the points
are transformed into points
Let be a given integer, and let be N independent random variables, uniformly distributed in the respective rectangles For every we use samples of and define the Monte Carlo estimate of to be
The Monte Carlo estimate for the integral
is obtained by summing
all the estimates for the integrals Such integration formulae were considered in [1], but only when has the smallest possible value This additional degree of freedom results in faster convergence of the resulting formulae.
3
Numerical Results
In this section we present numerical results that are obtained for calculating the value of the integral
The functions, that are considered here, are with different peculiarities. Often they are used for benchmarking of Monte Carlo and quasi-Monte Carlo algorithms. They are given as follows:
132
Emanouil I. Atanassov, Ivan T. Dimov, and Mariya K. Durchova
The first function has been used in [8] and [14] as a test in a context of rating point sets for quasi-Monte Carlo and Monte Carlo integration. The last three functions are a part of the test functions package proposed by Genz or in [13,15,19]. The parameters are divided into unaffective and affective parameters. The vector of affective parameters is scaled so that it satisfies the requirement
for the functions respectively, that depends only on the space dimensionality. In Table 1 we present numerical results from the approximate integration of the integral using the Monte Carlo and quasi-Monte Carlo version of the algorithm. The algorithms where tested for dimension 4, 5, 6, and 9. We did not compare our algorithm with crude Monte Carlo as in [6], because of its much slower convergence. From this table we made the conclusion, that the quasiMonte Carlo variant of the algorithm shows approximately the same accuracy as the Monte Carlo algorithm, i.e., for smooth functions.
A New Quasi-Monte Carlo Algorithm
133
In Table 2 and 3 we show numerical results for the other integrals in 5 dimensions. We again observe roughly the same probable error of the Monte Carlo and the quasi-Monte Carlo algorithm. All these results are obtained with the parameter (the number of quasi-random points in every small cube) equal to 40. In Table 4 we show the parallel efficiency of the algorithm. The computations for every small cube can be done in parallel, and thus the algorithm possesses a significant amount of natural parallelism. The results are achieved on a cluster of Intel Xeon 2.2 processors, using MPI.
4
Conclusions
We have developed a quasi-Monte Carlo method, which achieves order of convergence on smooth functions. The proposed quasi-Monte Carlo
134
Emanouil I. Atanassov, Ivan T. Dimov, and Mariya K. Durchova
method shows roughly the same accuracy as the Monte Carlo version, and also exhibits good parallel efficiency. However, the statistical aposteriory error estimation, based on the use of scrambled low-discrepancy sequences, is slightly more complicated and less reliable, than Monte Carlo methods. In our experiments we obtained good results by using the Sobol sequences. Note that the constructive dimensionality of the algorithm is relatively high - sm, and thus the integration method can be used for assessing the quality of distribution of other families of low-discrepancy sequences, i.e., for benchmarking purposes.
Acknowledgements Supported by the project of European Commission - BIS 21 under contract ICA1-CT-2000-70016 and by the Ministry of Education and Science of Bulgaria under contract NSF I-1201/02 and NSF MM-902/99.
References 1. E. Atanassov, I. Dimov. A new optimal Monte Carlo method for calculating in-
2. 3. 4.
5. 6.
7. 8. 9. 10.
11. 12. 13.
tegrals of smooth functions. Monte Carlo Methods and Applications, 5 2 (1999), 149–167. N.S. Bachvalov. On the approximate computation of multiple integrals. Vestnik Moscow State University, Ser. Mat., Mech., 4 (1959) 3–18. N. S. Bachvalov. Average Estimation of the Remainder Term of Quadrature Formulas. USSR Comput. Math. and Math. Phys., 1 1 (1961) 64–77. R. E Caflisch, W. Morokoff, A. B. Owen. Valuations of mortgage backed securities using Brownian bridges to reduce effective dimension. Journal of Computational Finance, 1 (1997) 27–46. S. Capstick, B. D. Keister. Multi dimensional Quadrature Algorithms at Higher Degree and/or Dimension, www.scri.fsu.edu/ ~capstick /papers/quad.ps. I. Dimov, A. Karaivanova, R. Georgieva, S. Ivanovska. Parallel Importance Separation and Adaptive Monte Carlo Algorithms for Multiple Integrals, In: I. Dimov, I. Lirkov, S. Margenov, Z. Zlatev Eds., Numerical Methods and Applications, Lecture Notes in Computer Science, 2542, Springer Verlag (2003) 99–107. M. Drmota, R. F. Tichy. Sequences, Discrepancies and Applications, Lecture Notes on Mathematics, Springer, Berlin, 1997, N 1651. K. Entacher, A. Uhl, S. Wegenkittl. Linear congruential generators for parallel Monte Carlo: the leap-frog case, Monte Carlo Meth. Appl., 4 (1998) 1–16. L. Kuipers, H. Niederreiter. Uniform distribution of sequences, John Wiley & sons, New York, 1974. N. Kjurkchiev, Bl. Sendov, A. Andreev. Numerical Solution of Polynomial Equations, P.G. Ciarlet and J. L. Lions (Eds.), Handbook of Numerical Analysis, Solution of Equations in (Part 2), 3, North-Holland, Amsterdam, NY, 1994. C. Van Loan, G. Golub. Matrix Computations, The John Hopkins University Press, Baltimore and London, third edition, 1996. A. B. Owen. Scrambled Net Variance for Integrals of Smooth Functions, Annals of Statistics, 25 4 (1997) 1541–1562. A. B. Owen. The dimension distribution and quadrature test functions, wwwstat.stanford.edu/ ~owen/reports, November, 2001.
A New Quasi-Monte Carlo Algorithm
135
14. W. Ch. Schmid, A. Uhl. Techniques for parallel quasi-Monte Carlo integration with digital sequences and associated problems, Math. and Comp. in Sim., 55 (2001) 249–257. 15. R. Schuerer. A comparison between (quasi-)Monte Carlo and cubature rule based method for solving high-dimensional integration problems, Math. and Comp. in Sim., 62 3–6 (2003) 509–517. 16. I. H. Sloan, H. Wozniakowski. When are quasi-Monte Carlo Algorithms efficient in high-dimensional integration, Journal of Complexity, 14 (1998) 1–33. 17. I. M. Sobol' . Monte Carlo Methods, Nauka, Moscow, 1973. 18. I. M. Sobol' , D. I. Asotsky. One more experiment on estimating high-dimensional integrals by quasi-Monte Carlo methods, Math. and Comp. in Sim., 62 3–6 (2003) 255–275. 19. http://www.math.wsu.edu /math / faculty /genz / homepage, Software / MULTST. 20. M. D. Takev. On Probable Error of the Monte Carlo Method for Numerical Integration, Mathematica Balkanica (New Series), 6 (1992) 231–235.
Monte Carlo Method for Multiple Knapsack Problem Stefka Fidanova CLPP – BAS, Acad. G. Bonchev, bl.25A, 1113 Sofia, Bulgaria
[email protected] Abstract. This paper describes Monte Carlo (MC) method for Multiple Knapsack Problem (MKP). The MKP can be defined as economical problem like resource allocation and capital budgeting problems. The Ant Colony Optimization (ACO) is a MC method, created to solve Combinatorial Optimization Problems (COPs). The paper proposes a Local Search (LC) procedure which can be coupled with the ACO algorithm to improve the efficiency of the solving of the MKP. This will provide optimal or near optimal solutions for large problems with an acceptable amount of computational effort. Computational results have been presented to assess the performance of the proposed technique.
1 Introduction There are many NP-hard combinatorial optimization problems for which it is impractical to find an optimal solution. Among them is the MKP. For such problems the reasonable way is to look for algorithms that quickly produce near-optimal solutions. ACO [1, 3, 2] is a MC method, created to solve COPs. It is a metaheuristic procedure for quickly and efficiently obtaining high quality solutions to complex optimization problems [7]. ACO algorithm can be interpreted as parallel replicated Monte Carlo systems [10]. MC systems [8] are general stochastic simulation systems, that is, techniques performing repeated sampling experiments on the model of the system under consideration by making use of a stochastic component in the state sampling and/or transition rules. Experimental results are used to update some statistical knowledge about the problem, as well as the estimate of the variables the researcher is interested in. In turn, this knowledge can be also iteratively used to reduce the variance in the estimation of the described variables, directing the simulation process toward the most interesting state space regions. Analogously, in ACO algorithms the ants sample the problem’s solution space by repeatedly applying a stochastic decision policy until a feasible solution of the considered problem is built. The sampling is realized concurrently by a collection of differently instantiated replicas of the same ant type. Each ant “experiment” allows to adaptively modify the local statistical knowledge on the problem structure. The recursive retransmission of such knowledge by means of stigmergy determines a reduction in the variance of the whole search process the so far most interesting explored transitions probabilistically bias future search, preventing ants to waste resources in not promising regions of the search. I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 136–143, 2004. © Springer-Verlag Berlin Heidelberg 2004
Monte Carlo Method for Multiple Knapsack Problem
137
The ACO algorithms were inspired by the observation of real ant colonies. Ants are social insects, that is, insects that live in colonies and whose behavior is directed more to the survival of the colony as a whole then to that of a single individual component of the colony. An important and interesting of ant colonies is how ants can find the shortest path between food sources and their nest. ACO is the recently developed, population-based approach which has been successfully applied to several NP-hard COPs [4]. One of its main ideas is the indirect communication among the individuals of a colony of agents, called “artificial” ants, based on an analogy with trails of a chemical substance, called pheromone which real ants use for communication. The “artificial” pheromone trails are a kind of distributed numerical information which is modified by the ants to reflect their experience accumulated while solving a particular problem. When construct a solution, at each step ants compute a set of feasible moves and select the best according to some probabilistic rules. The transition probability is based on the heuristic information and pheromone trail level of the move (usability of the move in the past). The rest of the paper is organized as follows: Section 2 describes the general framework for MKP as a COP. The search strategy of the local search method is explained in Section 3. Section 4 outlines the implemented ACO applied to MKP. In Section 5 experimental results over test problems are shown. Finally some conclusions are done.
2
Formulation of the Problem
The MKP has received wide attention from operation research community, because it embraces many practical problems. Applications include resource allocation in distributed systems, capital budgeting and cutting stock problems. In addition, MKP can be seen as a general model for any kind of binary problems with positive coefficients [6, 5]. The MKP can be thought as a resource allocation problem, where we have resources (the knapsacks) and objects. The object has a profit Each resource has its own budget (knapsack capacity) and consumption of resource by object We are interested in maximizing the profit, while working with a limited budget. The MKP can be formulated as follows:
There are constraints in this problem, so MKP is also called knapsack problem. Let and with for all A well-stated MKP assumes that and for all and Note that the matrix and vector are both non-negative.
138
Stefka Fidanova
In the MKP we are not interested in solutions giving a particular order. Therefore a partial solution is represented by and the most recent elements incorporated to S, need not to be involved in the process for selecting the next element. Moreover, solutions for ordering problems have a fixed length as we search for a permutation of a known number of elements. Solutions for MKP, however, do not have a fixed length. We define the graph of the problem as follows: the nodes correspond to the items, the arcs fully connect nodes.
3
The Local Search Strategy
The LS method (move-by-move method) [9] perturbs a given solution to generate different neighborhoods using a move generation mechanism. In general, neighborhoods for large-sized problems can be much complicated to search. Therefore, LS attempts to improve an initial solution by a series of local improving changes. A move-generation is a transition from a solution S to another one in one step. These solutions are selected and accepted according to some predefined criteria. The returned solution may not be optimal, but it is the best solution in its local neighborhood V(S). A local optimal solution is a solution with the local maximal possible cost value. Knowledge of a solution space is the essential key to more efficient search strategies. These strategies are designed to use this prior knowledge and to overcome the complexity of an exhaustive search by organizing searches across the alternatives offered by a particular representation of the solution. The main purpose of LS implementation is to speed up and improve the solutions constructed by the ACO. A practical LS strategy that satisfies the MKP requirements has been developed and coupled with ACO algorithm. The MKP solution can be represented by string with 0 for not chosen items and 1 for chosen items. In our LS procedure we will replace one of the 1 with 0 and one of the 0 with 1. The change in cost is completed and the swap is accepted or rejected according to the acceptance strategy.
4 ACO Algorithm for MKP Real ants foraging for food lay down quantities of pheromone (chemical cues) marking the path that they follow. An isolated ant moves essentially at random but an ant encountering a previously laid pheromone will detect it and decide to follow it with high probability and thereby reinforce it with a further quantity of pheromone. The repetition of the above mechanism represents the auto-catalytic behavior of real ant colony where the more the ants follow a trail, the more attractive that trail becomes. The ACO algorithm uses a colony of artificial ants that behave as co-operative agents in a mathematic space were they are allowed to search and reinforce pathways (solutions) in order to find the optimal ones. After initialization of the pheromone trails, ants construct feasible solutions, starting from random
Monte Carlo Method for Multiple Knapsack Problem
139
nodes, then the pheromone trails are updated. At each step ants compute a set of feasible moves and select the best one (according to some probabilistic rules) to carry out the rest of the tour. The transition probability is based on the heuristic information and pheromone trail level of the move. The higher value of the pheromone and the heuristic information, the more profitable is to select this move and resume the search. In the beginning, the ant do feasible moves and select the best one (according to some probabilistic rules) to carry out the rest of the tour. In the beginning, the initial pheromone level is set to a small positive constant value and then ants update this value after completing the construction stage. ACO algorithms adopt different criteria to update the pheromone level. In our implementation we use Ant Colony System (ACS) [3] approach. In ACS the pheromone updating stage consists of:
4.1
Local Update Stage
While ants build their solution, at the same time they locally update the pheromone level of the visited paths by applying the local update rule as follows:
Where is an amount of the pheromone on the arc of the graph of the problem, is a persistence of the trail and term can be interpreted as trail evaporation. The aim of the local updating rule is to make better use of the pheromone information by dynamically changing the desirability of edges. Using this rule, ants will search in wide neighborhood of the best previous solution. As shown in the formula, the pheromone level on the paths is highly related to the value of evaporation parameter The pheromone level will be reduced and this will reduce the chance that the other ants will select the same solution and consequently the search will be more diversified.
4.2
Global Updating Stage
When all ants have completed their solution, the pheromone level is updated by applying the global updating rule only on the paths that belong to the best solution since the beginning of the trail as follows:
where
is the cost (profit) of the best solution from the beginning. This global updating rule is intended to provide a greater amount of pheromone on the
140
Stefka Fidanova
paths of the best solution, thus intensifying the search around this solution. The transition probability to select the next item is given as:
where is a pheromone level on the arc is the heuristic and is the set of remaining feasible items. Thus the higher the value of the more profitable it is to include item in the partial solution. Let For heuristic information we use:
and
where and are parameters. Hence the objects with greater profit and less average expenses will be more desirable.
5
Experimental Results
This section reports on the computational experience of the ACS coupled with local search procedures using large MKP from “OR-Library” available within WWW access at http://mscmga.ms.ic.ac.uk/jeb/orlib. To provide a fair comparison for the above implemented ACS algorithm, a predefined number of iterations, K=500, is fixed for all the runs. The developed technique has been coded on C + + language and implemented on a Pentium 3 (450 MHz). Because of the random start of the ants we can use less ants then the number of the nodes (objects). After the tests we found that 10 ants are enough to achieve good results. Thus we decrease the running time of the program. The results on the Figures show the advantage to use local search procedures. The reported results are an average over 10 runs of the program. The chosen LS strategy appears to be very effective for MKP. For all tested problems our algorithm achieved, in some of the runs, the best found results in the literature. In all tested problems achieved results using LS procedure are better than without local search.
6
Conclusion
In this paper a local search procedure have been developed. The comparison of the performance of the ACS coupled with this procedure applied to different MKP problems are reported. The results obtained are encouraging and the ability of the developed technique to generate rapidly high-quality solutions for MKP can be seen. For future work another important direction for current research is to try different strategies to explore the search space more effectively and provide good results.
Monte Carlo Method for Multiple Knapsack Problem
141
Fig. 1. The figures show the average solution quality per iteration over 10 runs
Acknowledgments Stefka Fidanova was supported by the European Community program “Center of Excellence” under contract number No ICA1-2000-70016.
References 1. Dorigo, M., Di Caro, G.: The Ant Colony Optimization metaheuristic. In: Corne,
D., Dorigo, M., Glover, F.(eds.): New Idea in Optimization, McGrow-Hill (1999) 11–32. 2. Dorigo, M., Di Caro, G., Gambardella, L. M.: Ant Algorithms for Distributed Discrete Optimization. J of Artificial Life 5 (1999) 137–172.
142
Stefka Fidanova
Fig. 2. The figures show the average solution quality per iteration over 10 runs
3. Dorigo, M., Gambardella, L.M.: Ant Colony System: A cooperative Learning Ap-
4. 5. 6.
7.
proach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation 1 (1999) 53–66. Gambardella, M. L., Taillard, E. D., Dorigo, M.: Ant Colonies for the QAP. J of Oper. Res. Soc. 50 (1999) 167–176. Kochenberger, G., McCarl, G., Wymann, F.: A Heuristic for General Integer Programming. J of Decision Sciences 5 (1974) 34–44. Leguizamon, G., Michalevich, Z.: A New Version of Ant System for Subset Problems In: Proceedings of Int. Conf. on Evolutionary Computations, Washington (1999). Osman, I. H., Kelley, J. P.: Metaheuristic: An Overview. In: Osman, I. H., Kelley, J.P. (eds.), Metaheuristic: Theory and Applications, Kluwer Academic Publishers (1996).
Monte Carlo Method for Multiple Knapsack Problem
143
8. Rubinstein, R. Y.: Simulation and the Monte Carlo Method. John Wiley & Sons
(1981). 9. Schaffer, A. A., Yannakakis, M.: Simple Local Search Problems that are Hard to
Solve. Society for Industrial Applied Mathematics Journal on Computing, Vol 20 (1991) 56–87. 10. Strelsov, S., Vakili, P.: Variance Reduction Algorithms for Parallel Replicated Simulation of Uniformized Markov chains. J. of Discrete Event Dynamic Systems: Theory and Applications, 6(1996) 159–180.
Importance Separation for Solving Integral Equations Rayna Georgieva and Sofiya Ivanovska CLPP - Bulgarian Academy of Sciences Acad. G. Bonchev, Bl.25A, 1113 Sofia, Bulgaria {rayna,sofia}@copern.bas.bg
Abstract. In this paper we describe and study importance separation Monte Carlo method for integral equations. Based on known results for integrals, we extend this method for solving integral equations. The method combines the idea of separation of the domain into uniformly small subdomains (adaptive technique) with the Kahn approach of importance sampling. We analyze the error and compare the results with the crude Monte Carlo method.
1 Introduction An important advantage of Monte Carlo methods (MCMs) is that they allow to find directly the unknown functional of the solution of integral equations with a number of operations necessary to calculate the solution of an integral equation only in one point of the domain [11]. Much of the efforts to improve MCM are in construction of variance reduction methods which speed up the computation (see [2]). In [6, 8, 9] such method for numerical integration called importance separation (IS) is presented and studied. This method has the best possible rate of convergence for a certain class of functions (see [1]), but its disadvantage is that it gives better accuracy only for low dimensions. The problem for calculation of a linear functional of the solution of an integral equation can be transformed into approximate evaluation of a finite number of integrals (linear functionals of iterative functions) [6]. We apply the IS method for each of the integrals and extend the study of its properties. We also study the conditions under which the IS method has an advantage over other methods. We compare these results with Crude Monte Carlo method (CrMCM) for integrals and Monte Carlo method for integral equations (MCM-int.eq.) (see [11]).
2
Formulation of the Problem
Consider the Fredholm integral equation of the second kind:
or I. Lirkov et al. (Eds.): LSSC 2003, LNCS 2907, pp. 144–152, 2004. © Springer-Verlag Berlin Heidelberg 2004
Importance Separation for Solving Integral Equations
145
are given functions and is an unknown function, is a bounded domain). We are interested in Monte Carlo method for evaluation of linear functionals of the solution of the following type:
It is assumed that for solving integral equations:
We can apply successive approximation method
where It is known that the condition is a sufficient condition for convergence of the Neumann series. Thus, when this condition is satisfied, the following statement holds:
Therefore,
An approximation of the unknown value Neumann series (2) for sufficiently large
can be obtained using a truncated
So, we transform the problem for solving integral equations into a problem for approximate evaluation of a finite number of multidimensional integrals. We will use the following denotation where is a value, obtained after integration over It is obvious that the calculation of the estimate can be replaced by evaluation of a sum of linear functionals of iterative functions of the following type which can be presented as:
where function
If we denote by
the integrand
146
Rayna Georgieva and Sofiya Ivanovska
then we will obtain the following expression for (3):
So, from now on we will consider the problem for approximate calculation of multiple integrals of the type (4). We will first review briefly the most widely used Monte Carlo methods for integrals and integral equations. It is well-known that Monte Carlo methods reduce the problem to the approximate calculation of mathematical expectation which coincides with the unknown functional defined by (1).
3 3.1
Monte Carlo Methods Crude Monte Carlo Method for Integrals
The Monte Carlo quadrature formula is based on the probabilistic interpretation of an integral. If is an uniformly distributed sequence in G, then the Monte Carlo approximation to the integral is
with integration error volume of G.
3.2
where V(G) is the
Monte Carlo Method for Integral Equations
It is known (see [11]) that the approximate calculation of linear functionals of the solution of an integral equation brings to the calculation of a finite sum of linear functionals of iterative functions First, in we construct a random trajectory (Markov chain) of length starting in state
according to the initial and transition probabilities. The functions and satisfy the requirements for non-negativeness, to be acceptable to function and the kernel respectively and for any From the above supposition on the kernel and the well-known fact that