Send mail to: mgnet@cs.yale.edu for the digests or bakeoff mgnet-requests@cs.yale.edu for comments or help Anonymous ftp repository: www.mgnet.org (128.163.209.19) Current editor: Craig Douglas douglas-craig@cs.yale.edu World Wide Web: http://www.mgnet.org or http://casper.cs.yale.edu/mgnet/www/mgnet.html or http://www.cerfacs.fr/~douglas/mgnet.html or http://phase.etl.go.jp/mgnet or http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 10, Number 4 (approximately April 30, 2000) Today's topics: Next Issue Interactive Numerical Examples in ETNA Job in Numerical Analysis Two Open Positions at the University of Zurich Copper Mountain 2000 Paper (Freund) Copper Mountain 2000 paper (Notay) Copper Mountain Conference on Iterative Methods: Talks ------------------------------------------------------- Date: Sat, 13 May 2000 09:56:28 +0500 From: Craig DouglasSubject: Next Issue The next issue needs to come out on around June 1. Please contribute items now or as soon as possible. I will be maintaining an active new newsletter on the web as soon as material is available instead of waiting until the issue needs to go out. ------------------------------------------------------- Date: Thu, 6 Apr 2000 10:51:14 -0400 (EDT) From: Lothar Reichel Subject: Interactive Numerical Examples in ETNA Many papers in computational mathematics contain numerical examples that illustrate the theory discussed, or the virtues or shortcomings of numerical methods. The examples, in general, depend on certain parameters, whose values are chosen by the author of the paper. A reader may be interested in studying the examples for other parameter values, but typically this is not straightforward. Computer programs may have to be written or requested from the author of the paper. The Electronic Transactions on Numerical Analysis (ETNA) makes it possible to publish interactive examples that allow readers to vary parameter values. Presently, two papers J. Baglama, D. Calvetti and L. Reichel, Fast Leja points, ETNA 7 (1998), pp. 124-140, R. S. Varga and A. Krautstengl, On Gersgorin-type problems and ovals of Cassini, ETNA 8 (1999), pp. 15-20, illustrate this feature. Click on the ``interactive supplement'' for these papers for a demonstration. Authors of papers accepted for publication in ETNA are encouraged to supply interactive examples. The ETNA staff will assist with the design and Java programming of the examples. ETNA is available at http://etna.mcs.kent.edu and at mirror sites. In addition volumes 1-10 of ETNA are available on a new CDROM. The ETNA CDROM contains papers published in ETNA 1993-2000, interactive examples, a search engine and web browsers. A limited number of CDROMs are available for $10 each. Please send e-mail to etna@mcs.kent.edu if you would like your own portable copy of ETNA on a CDROM. ------------------------------------------------------- Date: Thu, 13 Apr 2000 12:00:26 +0100 (BST) From: Iain Duff Subject: Job in Numerical Analysis RESEARCH POSITION IN NUMERICAL ANALYSIS Rutherford Appleton Laboratory, Oxfordshire Fixed Term (4 years with possible extension) A research position is available within the Numerical Analysis Group at the Rutherford Appleton Laboratory of the Central Laboratory of the Research Councils. Duties will involve performing independent but relevant research, with the goal of publication in the open literature and presenting the results at national and international conferences. Duties will include the production of high-quality numerical software connected with this research and the promotion of the Group's activities within the UK academic community. There will also be the opportunity to lecture in occasional Laboratory courses on numerical analysis and computing areas. The ideal candidate will hold a doctoral degree in numerical analysis or a closely related mathematical area. Preference will be given to candidates with a high international profile whose research interests overlap those of existing members of the Group, particularly in the solution of large-scale linear or nonlinear equations, and of eigenvalue and numerical optimization problems. Although the successful applicant will be expected to interact with other members of the Group, strong evidence of the ability to work independently will be expected. Considerable experience of programming in Fortran and of using standard numerical analysis libraries such as BLAS and LAPACK is essential. Additional programming skills will be considered an advantage. Further information on the Group can be found on http://www.cse.clrc.ac.uk/Group/CSENAG The post will be available from the beginning of May 2000 and applicants should indicate when they would be able to take up the position should their application be successful. The salary range is between 18,620 and 26,600 pounds (Band 5) or 23,240 and 33,200 pounds (Band 4), depending on qualifications and experience. A non-contributory pension scheme and a generous leave allowance are offered. Application forms can be obtained from: Operations Group, HR Division, Rutherford Appleton Laboratory, Chilton, Didcot, Oxfordshire, OX11 0QX. Telephone (01235) 445435 (answerphone) quoting reference VN1920, or e-mail recruit@rl.ac.uk. More information about CCLRC and application forms are available from CCLRCs World Wide Web pages at http://www.cclrc.ac.uk All applications must be returned by 27 April 2000. The CCLRC is committed to Equal Opportunities and to achieving the Investors In People standard. A no smoking policy is in operation. ------------------------------------------------------- Date: Mon, 10 Apr 2000 11:07:29 +0100 From: Lili Koloszar Subject: Two Open Positions at the University of Zurich The Department of Mathematics at the University of Zurich has the following two open positions. Post-doc in Numerical Analysis and Scientific Computing The position is integrated in the Numerical Analysis Research Group, and the duties include independent research in the field of numerical analysis for solving PDEs with a view towards further scientific qualification. Participation in the current research projects of the Numerical Analysis Group and in their teaching activities is required. Pre-requisites: Ph.D. in mathematics and research experience in the field of applied and numerical analysis. Scientific Assistant in Numerical Analysis and Scientific Computing The duties involve working on a research project for the numerical solution of partial differential equations on complicated domains by multigrid methods. The project is sponsored by the Swiss Nationalfonds and should lead to a Ph.D. thesis. Participation in teaching activities (in German) is also required. Pre-requisites: University degree in mathematics, computer science or one of the natural sciences. Please send your application to Universitaet Zurich Institut fur Mathematik Herrn Prof. Dr. S. Sauter Winterthurerstr. 190 CH-8057 Zurich Switzerland Tel.: ++41 (0) 1 635 5831; eMail: stas@amath.unizh.ch ------------------------------------------------------- Date: Sun, 02 Apr 2000 21:43:31 -0400 From: Roland Freund Subject: Copper Mountain 2000 Paper (Freund) Krylov-Subspace Iterations for Reduced-Order Modeling

in VLSI Circuit Simulation Roland W. Freund Bell Laboratories Room 2C-525 700 Mountain Avenue Murray Hill, NJ 07974-0636 Abstract Traditional VLSI circuit simulation is based on the numerical solution of large-scale stiff nonlinear systems of differential-algebraic equations (DAEs). Numerical techniques for such DAEs require the repeated solution of large sparse systems of linear equations, and iterative methods, such as Krylov-subspace algorithms, seem to be predestined to the solution of these linear systems. However, for various reasons, standard SPICE-like circuit simulators employ direct methods, rather than iterative methods. Nevertheless, the continuing evolution of VLSI circuits has now come to a point where Krylov-subspace methods are finally becoming mainstream tools in circuit simulation. More precisely, today, Krylov-subspace iterations are employed to generate reduced-order models of large linear subsystems of DAEs that describe large linear subcircuits of the VLSI circuit to be simulated. In this talk, we explain why and how Krylov-subspace methods are used for reduced-order modeling in VLSI circuit simulation. We discuss various desirable and in part conflicting properties of the reduced-order models, such as high approximation accuracy, stability, and passivity, and show how to achieve these properties by means of Krylov-subspace iterations. Numerical results for a variety of circuit examples are presented. Editor's Note: See http://www.mgnet.org/mgnet-cm2000.html for the full ------------- paper. ------------------------------------------------------- Date: Mon, 17 Apr 2000 15:18:43 +0200 (MEST) From: Yvan NotaySubject: Copper Mountain 2000 paper (Notay) Flexible Conjugate Gradients Yvan Notay Abstract We analyze the conjugate gradient method with preconditioning slightly variable from one iteration to the next. To maintain the optimal convergence properties, we consider a variant proposed by Axelsson that performs an explicit orthogonalization of the search directions vectors. For this method, which we refer to as flexible conjugate gradient, we develop a theoretical analysis that shows that the convergence rate is essentially independent of the variations in the preconditioner as long as the latter are kept sufficiently small. We further discuss the real convergence rate on the basis of some heuristic arguments supported by numerical experiments. Depending on the eigenvalue distribution corresponding to the fixed reference preconditioner, several situations have to be distinguished. In some cases, the convergence is as fast with truncated versions of the algorithm or even with the standard conjugate gradient method, whereas quite large variations are allowed without too much penalty. In other cases, the flexible variant effectively outperforms the standard method, while the need for truncation limits the size of the variations that can be reasonably allowed. Editor's Note: See http://www.mgnet.org/mgnet-cm2000.html for the full ------------- paper. ------------------------------------------------------- Date: Mon, 10 Apr 2000 12:26:12 +0500 From: Craig Douglas Subject: Copper Mountain Conference on Iterative Methods: Talks This is the list of talks that were scheduled to take place at the Copper Mountain Conference on Iterative Methods, which was held from April 2-7. The list was scanned from the paper program, so please do not laugh too hard if there are some oddities that I did not catch. Also, if you gave a talk that is not listed, please send me the title. M. Adams Evaluation of a Geometric and an Algebraic Multigrid Method on 3D Finite Element Problems in Solid Mechanics P. Arbenz On Computing Some of the Principal Eigenfrequencies of Cavity Resonators C. Aro Iterative Solver Performance on Algebraically Reduced Implicit Mechanical Linear Systems D. Aruliah Preconditioning Strategies for Low Frequency Electromagnetics Simulations T. Austin A Divergence-Free Relaxation Scheme in an H^1-Finite Element Space A. Baker Reducing Memory Access Costs: Variants of GMRES with Efficient Data Re-use P. Barton Sensitivity Analysis of Hybrid Systems: Theory and Numerical Implications V. Baryamureeba Solution of Robust Linear Regression Problems by Preconditioned Conjugate Gradient Type Methods M. Benzi On Some New Developments in Approximate Inverse Preconditioning M. Berndt On a Multilevel Solver That Utilizes Singular Basis Functions for the Solution of the Diffusion Equation With Discontinous Coefficient H. Branden A Note on Prasitic Solutions J. Brandts Calculation of Invariant Subspaces of Large and Sparse Matrices. M. Brezina Algebraic Multigrid for Problems with Discontinuous Coefficients Z. Cai Multigrid Method for the Poisson Eauation with Corner Singularities E. Chow Performance Charateristics of Least Squares Sparse Approximate Inverse Preconditioners A. Codd First-order System Least Squares (FOSLS) for Elliptic Grid Generation (EGG) T. Chartier Element Based Algebraic Multigrid (AMGe) J. Cullum Algebraic Multigrid: Accelerating the Convergence C. Dawson Time-splitting Methods for Chemically Reactive Transport H. DeGersem A Multigrid Algorithm for Quasistatic Electromagnetic Simulation E. de Sturler Improving the Convergence of the Jacobi-Davidson Algorithm B. Diskin Efficient Highly Parallel Multigrid Methods for the Convection Equation M. Dorobantu CFD Code Convergence Diagnostics and Acceleration Using the Recursive Projection Methods C. Douglas Almost Fully Utilized Caches for Iterative Methods Z. Drmac Perturbation Theory and Iterative Summetric Eigensolvers V. Druskin Gaussian Spectral Rules for Second Order Finite-Difference Schemes V. Eijkhout The Weighted Distributed Modification ILU Factorisation H. Elman Performance and Analysis of Saddle Point Preconditioners for the Discrete Steady-State Navier-Stokes Equations M. Embree Invariant Subspace Convergence for Amoldi's Method Equation O. Ernst Acceleration Strategies for Restarted Minimal Residual Methods R. Falgout Sparse Multiple Semicoarsened Grids R. Freund Krylov-Subspace Iterations for Reduced-Order Modeling in VLSI Circuit Simulation J. Fuhrmann Finite Volume Methods for Systems of Viscous Conservation Laws: Numerical Analysis and Software E. Gallopoulos On the Computational Effectiveness of Transfer Function Approximations to the Matrix Pseudospectrum S. Goossens Mortar Projection in Overlapping Composite Mesh Difference Methods C.-H. Guo Iterative Solution of a Matrix Equation Arising in Stochastic Control A. Grama Error Controlled Multipole Methods for Arbitrary Particle Distributions E. Haber On the Solution of the Linear Systems Which Evolve From Large Scale Inverse Problems M. Heinkenschloss Inexact Sequential Quadratic Programming Methods for the Solution of Inverse Problems Governed by PDEs L. Hemmingsson-Franden Semi Circulant Approximations in Preconditioners for Incompressible Flow Problems V.E. Henson Element-free AMGe: General Algorithms for Computing Interpolation Weights M. Heroux Solving Complex-valued Linear Systems via Equivalent Real Formulations A. C.-W. Ho Iterative Method for Robin Problems M. Hochstenbach JDSUD: A Jacobi-Davidson Like SVD Method S. Holgren Convergence Acceleration for the Euler Equations G. Horton An AMG-Like Solution Method for Markov Chains M. Huhtanen Hermitian Lanczos Method for Normal Matrices L. Jenkins Aggregation-Based Domain Decomposition Methods for Unsaturated Flow II: Theory and Convergence J. Jones Preconditioners for Newton-Klylov Solvers of Richards' Equation C. Keller Constraint Preconditioning for Indefinite Linear Systems T. Kelley Aggregation-Based Domain Decomposition Methods for Unsaturated Flow 1: Motivation and Design C. Kees Multilevel Schwarz Preconditioners for Two- and Three-phase Flow in Porous S. Kim Finite Element Preconditioning Cubic Spline Collocation Method of Elliptic Equations L. Knizhnennai Lanezos Method and Pad~-Chebyshev Approximation of Markov Functions D. Knoll On Newton-Krylov Methods in Solidifying Flow Applications A. Knyazev Toward the Optimal Preconditioned Eigensolver J. Korsawe Nonlinear First Order Systems Least Squares Finite Element Multilevel Computations: Extended Relaxation in H (div) D. Lahaye Solving Magnetics Field - Electric Circuit Coupled Systems R. Larsen Iterative Algorithms for Least Squares Problems with Multiple Right-hand Sides E. Larsson Parallelization of a Domain Decomposition Method for the Helmholtz Equation R. Lehoucq A Penalized Finite Element Method for Pure Neumann Problem L. Little Domain Decomposition of Solid-Liquid Flows D. Loghin A Fundamental Solution Preconditioner for the Navier-Stokes Equations L. Machiels Output Bounds for Partial Differential Equations: Application to Reduced Order Approximations H. MacMillan First-Order Systems Least Squares for Electrical Impedance Tomography S. McCormick Least-Squares Methods for Partial Differential Equations G. Meurant On the Perturbation of the Incomplete Cholesky Factorization J. More TAO: Toolkit for Advanced Optimization R. Morgan An Algorithm for Outlining the Spectrum of a Large Matrix and Determining Multiplicity of Eigenvalues B. Morini A Trust Region Method for Bound-Constrained Nonlinear Systems V. Mousseau Newton-Krylov Methods for Time Accurate Solution of Multi-Physics Hyperbolic Systems O. Nevanlinna Krylov Subspace and Low Rank Perturbations K. Neymeyr A Geometric Convergence Theory for Preconditioned Inverse Iteration Y. Notay Conjugate Gradient with Variable Preconditioning V. Pan Newton's Structured Matrix Iteration S. Parter Preconditioning Legendre Spectral Collocation Methods for Elliptic Problems: Finite Difference Operators and Finite Element Operators J. Pasciak Nonconforming Approximation Methods Based on Nonmatching Grids M. Pernice A Newton-Krylov-Multigrid Method for the Incompressible Navier-Stokes Equations L. Petzold Sensitivity Analysis and Software for Large-Scale Differential-Algebraic Systems A. Pothen A Parallel Algorithm for Incomplete Factorization Preconditioning M. Putti Iterative Methods for the Partial Symmetric Eigenproblems D. Quinlan Elliptic Solvers with Adaptive Mesh Refinement on Complex Geometries A. Ramage Iterative Convergence for Stabilised Finite Element Discretisations of Advection-Diffusion Problems R. Renaut Iterative Determination of Kinetic Constants from PET Data Utilizing Total Least Squares Estimates U. Ruede Adaptive Multigrid in Space and Time J. Ruge FOSPACK: A FOSLS/AMG Package Y. Saad Parallel Solution of Eigenvalue Problems in Electronic Structure Calculations E. W. Sachs An Indefinite Preconditioner for Quadratic Control Problems S.A. Salvini Sparse Iterative Solvers for Shared Memory Parallelism V. Sana Preconditioning Techniques for the Genrealized Navier Problem M. Shaskov Mimetic Discretizations of Diffusion Equation and Constructions of Preconditioners M. Sosonkina Rational Approximation Preconditioners for General Sparse Linear Systems G. Starke A Levenberg-Marquardt Method for Nonlinear Least-Squares Finite Element Computations A. Stathopoulos A Case for a Biorthogonal Jacobi-Davidson Method: Restarting and Correction S. Sundberg Parallel Semi-Toeplitz Preconditioners for Combustor Flows P. Sunqvist Preconditioners based on fundamental solutions D. Swesty Parallelizable Preconditioners for Multigroup Flux-limited Diffusion Problems D. Szyld Algebraic Theory of Additive and Multiplicative Schwarz T. Tefy Preconditioned Newton GMRES Methods for Non-Linear Systems of PDE's of Unsteady Compressible Fluid Flow M. Tocci Sensitivity Analysis using Inexact Newton Methods V. Tolstykh New First-Order Algorithms for High-Dimensional Quadratic Optimization A. Toselli Neumann-Neumann and Feti Preconditioners for Edge Element Approximation of Maxwell's Equation N. Trefethen Generalizing Eigenvalue Theorems to Pseudospectia Theorems M. Trummer Preconditioning Spectral Methods for First Order Equations H.M. Tufo A Parallel Direct Solver Package for Coarse Grid Problems H. van der Vorst Ritz and Harmonic Ritz Approximates P. Vassilevski Graph based multilevel algorithms for Preconditioning Finite Element Problems M. Verbeek Smoother Dependent Interpolation for AMG J. Vogel FQMR: A Flexible Quasi-Minimal Residual Method with Inexact Preconditioning K. Vuik Deflated ICCG Applied to Problems with Extreme Contrasts in the Coefficients A. Wathen Preconditioning Constrained Systems M. Wheeler A Problem Solving Environment for Coupling Multiphysics and Multiple Domains in Porous Media R. Wienands On Three-grid Fourier Analysis of Multigrid J. Wilson Efficient Solver for Mixed and Control- Volume Mixed Finite Element Methods in Three Dimensions C. Woodward Implicit Solution of Radiation-Diffusion Problems Using Newton-Krylov Multigrid Methods T. Wright Computation of Pseudospectra Using ARPACK and EIGS C. Yang Large-Scale Normal Coordinate Analysis for Molecular Structures D. Yang Accurate Numeric Methods for Interface Problems with Strongly Discontinous Coefficients U. Yang BoomerAMG: a Parallel Algebraic Multigrid Solver: Implementation and Enhancements J. Zhang Adaptive ILU Preconditioning Strategies in Semiconductor Process Modeling ------------------------------ End of MGNet Digest **************************