Send mail to: mgnet@cs.yale.edu for the digests or bakeoff mgnet-requests@cs.yale.edu for comments or help Current editor: Craig Douglas douglas-craig@cs.yale.edu Anonymous ftp repository: casper.cs.yale.edu (128.36.12.1) World Wide Web: http://na.cs.yale.edu/mgnet/www/mgnet.html or http://www.cerfacs.fr/~douglas/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 6, Number 3 (approximately March 31, 1996) Today's topics: Paper by Bakhvalov and Knyazev Fifth European Multigrid Conference (EMG 96) Copper Mountain Conference on Iterative Methods Preprints Some BibTeX Entries ------------------------------------------------------- Date: Mon, 4 Mar 1996 14:29:13 -0700 From: aknyazev@tiger.cudenver.edu (Andrew Knyazev) Subject: Paper by Bakhvalov and Knyazev Preconditioned Iterative Methods in a Subspace for Linear Algebraic Equations with Large Jumps in the Coefficients Nikolai S. Bakhvalov Institute of Numerical Mathematics Russian Academy of Sciences Moscow, Russia Andrew V. Knyazev Department of Mathematics University of Colorado at Denver P.O. Box 173364 Campus Box 170 Denver, CO 80217-3364 Abstract We consider a family of symmetric matrices $A_\omega=A_0+\omega B$, with a nonnegative definite matrix $A_0$, a positive definite matrix $B$, and a nonnegative constant $\omega\le 1$. Small $\omega$ leads to a poor conditioned matrix $A_\omega$ with jumps in the coefficients. For solving linear algebraic equations with the matrix $A_\omega$, we use standard preconditioned iterative methods with the matrix $B$ as a preconditioner. We show that a proper choice of the initial guess makes possible keeping all residuals in the subspace IM($A_0$). Using this property we estimate, uniformly in $\omega$, the convergence of the methods. Algebraic equation of this type arise naturally as finite element discretizations of boundary value problems for PDE with large jumps of coefficients. For such problems the rate of convergence does not decrease when the mesh gets finer and/or $\omega$ tends to zero; each iteration has only a modest cost. The case $\omega=0$ corresponds to the fictitious component/capacitance matrix methods. Editor's Note: in mgnet/papers/Bakhvalov-Knyazev/jumps.ps.gz and ------------- .../jumps.abs ------------------------------------------------------- Date: Thu, 28 Mar 1996 11:02:29 +0100 From: Sekretariat des ICA3Subject: Fifth European Multigrid Conference (EMG 96) University of Stuttgart Institut fuer Computeranwendungen III Pfaffenwaldring 27 D-70569 Stuttgart Tel.: ++49-711-685 7091 Fax: ++49-711-685 7000 Would you please include the following conference in your "Information about future conferences": Fifth European Multigrid Conference (EMG 96) October 1 - 4, 1996, University of Stuttgart, Germany Further information and registration at URL: http://www.ica.uni-stuttgart.de/formular/ica3formular.html Thank you in advance. Gunter Faust Editor's Note: Here is what I found in the web page, which is now ------------- archived in conferences/emg96.txt University of Stuttgart, Institut fur Computeranwendungen (ICA) EMG '96 Fifth European Multigrid Conference Oct. 1-4, 1996 Stuttgart The Institut fur Computeranwendungen (ICA) of Stuttgart University, in cooperation with the GAMM Committee on Scientific Computing, SFB 359 and 404 and the research network WiR Ba-Wu, is organising the European Multigrid Conference '96. Earlier European Multigrid Conferences were held in Cologne in 1981 and 1985, in Bonn in 1990 and in Amsterdam in 1993. The conference provides a forum for the presentation and discussion of recent research in the general area of multigrid methods. Participation will be worldwide. Chairmen: Wolfgang Hackbusch, Kiel Gabriel Wittum, Stuttgart Organisation: Gunter Faust, Prudence Lawday ICA, Universitat Stuttgart, 70569 Stuttgart Phone: ++49-711-685-7090 Fax: ++49-711-685-7000 email: emg96@ica.uni-stuttgart.de Date: October 1st - 4th, 1996 Location: Institut fur Computeranwendungen, Pfaffenwaldring 27, 70569 Stuttgart Germany Topics: Multigrid Methods: robustness, adaptivity, wavelets, parallel methods and software, applications in computational fluid dynamics, porous media flow, optimisation, computational mechanics and statistical physics. Invited speakers (tentative): R. Bank (La Jolla), W. Dahmen (Aachen), P. Deuflhard (Berlin), M. Griebel (Munich), P.W. Hemker (Amsterdam), R. Kornhuber (Berlin), U. Langer (Linz), G. Mack (Hamburg), J. Mandel (Boulder), D. Mavriplis (Ames), A. Reusken (Eindhoven), K. Stuben (Bonn) Abstracts: Please send an abstract of your proposed lecture by June 1st, 1996. The collection of abstracts will be available at the conference. Notice of acceptance will be given by July 15th, 1996. The conference language is English. Proceedings: Invited lectures and a number of selected presentations will appear as full papers in the conferece proceedings to be publish-ed by Birkhauser. Participants may order the volume at a reduced price of 100,- DM on the registration form. Further presentations will be published as full papers by ICA. Registration: Please mail the enclosed form or register via http://www.ica.uni-stuttgart.de. Registration is valid only after full payment of the conference fee. Conference fee: DM 400,- payable by Aug. 1st 1996 or DM 500,- after this date. The fee includes admission to all sessions, lunches and coffee breaks, the reception, the conference dinner and the collection of abstracts. Payments: All payments, net of all charges, are to be made in Deutschmarks by bank transfer to: Universitat Stuttgart, Baden-Wurtt.-Bank Stuttgart, bank code 600 200 30, account no. 105 4611 700, specifying your name, "EMG96" and "Titel 11186, BA 4715". Stuttgart: Stuttgart is an attractive modern city situated in a thriving region between the Black Forest and the Schwabische Alb. It is a town of fascinating contrasts: on the one hand, an industrial metropolis with world-famous firms and, on the other hand, a city of parks and open spaces - there are even vineyards extending right into the centre. The conference will take place at ICA on the university campus in Vaihingen, just a short ride from the inner city. Accommodation: Hotel rooms can be booked through: Stuttgart-Marketing, Postfach 104436, 70173 Stuttgart, Tel.: 0711/2228-233 or -246; Fax: 0711/2228-251 (please mention EMG '96). Getting here: The conference venue is within easy reach of both the airport (10 minutes by either taxi or metro) and the main railway station (15 minutes by either taxi or metro). More detailed information will be sent to all participants after registration. Social events: A conference reception will be held on the evening of Wednesday, 2nd October. On the a fternoon of Thursday, 3rd October, there will be an excursion followed in the evening by the conference dinner. A programme for accompanying persons will be organised if there is sufficient interest (please see registration form). * * * * * University of Stuttgart, Institut fur Computeranwendungen (ICA) Registration EMG '96 Fifth European Multigrid Conference Oct. 1-4, 1996 Stuttgart Institut fur Computeranwendungen III Universitat Stuttgart EMG '96 Pfaffenwaldring 27 70569 Stuttgart Germany Please, accept my registration for EMG 96: Name: ______________________________________________________________ Affiliation: ______________________________________________________________ Address: ______________________________________________________________ ______________________________________________________________ Country: ______________________________________________________________ E-mail: ______________________________________________________________ Fax: ______________________________________________________________ Phone: ______________________________________________________________ I would like to receive a copy of the proceedings volume at a reduced price of DM 100,- YES I am interested in the programme for accompanying persons YES I have transferred the following sum to the ICA bank account: DM 400,- registration fee until Aug. 1st _________ DM 500,- registration fee after Aug. 1st _________ DM 100,- for the proceedings volume _________ ------------------------------------------------------- Date: Sun, 31 Mar 1996 14:26:19 -0500 (EST) From: Craig Douglas Subject: Copper Mountain Conference on Iterative Methods Preprints In the directory, mgnet/Conferences/CMCIM96, are a number of abstracts and preprints from the forthcoming (next week) conference. This will be set up similarly to the multigrid conferences held on odd years. Particiapants can download files to the machine casper.cs.yale.edu. Please put files in the directory mgnet/incoming/cmcim96/YourLastName. I will move the file(s) once I see them. Here is what is in the directory so far: Program.gz J. M. Banoczi and C. T. Kelley A Multilevel Method for Conductive-Radiative Heat Transfer banoczi-kelley.abs banoczi-kelley.ps.gz A. Basermann, B. Reichel, and Schelthoff Parallel Preconditioning Techniques for Sparse CG Solvers basermann-reichel-schelthoff.abs.ps.gz M. Benzi and M. Tuma Approximate Inverse Preconditioning of Iterative Methods for Nonsymmetric Linear Systems benzi-tuma.abs benzi-tuma.ps.gz S. W. Bova and G. F. Carey Iterative Solution of the Semiconductor Device Equations bova-carey.ps.gz H.-J. Bungartz A unidirectional approach for d-dimensional finite element methods of higher order on sparse grids bungartz.abs bungartz.ps.gz Z. Cai, T. A. Manteuffel, S. F. McCormick, and S. V. Parter First Order System Least Squares for the Pure Traction Problem in Planar Linear Elasticity cai-manteuffel-mccormick-parter.abs cai-manteuffel-mccormick-parter.ps.gz H. Choi and D. B. Szyld Threshold Partitioning of Sparse Matrices and Applications to Markov Chains choi-szyld.abs choi-szyld.ps.gz M. Clemens and T. Weiland Iterative Methods for the Solution of Very Large Complex Symmetric Linear Systems of Equations in Electrodynamics clemens-weiland.ps.gz X. Feng A Mixed Finite Element Domain Decomposition Method for Nearly Elastic Wave Equations in the Frequency Domain feng.abs feng.ps.gz P. A. Gray Iteration Schemes for Parallelizing Models of Superconductivity gray.abs gray.ps.gz G. Horton On the Multi-Level Solution Algorithm for Markov Chains horton.abs horton.ps.gz C. T. Kelley, C. T. Miller, and M. D. Tocci Method of Lines Solution of Richards' Equation kelley-miller-tocci.abs kelley-miller-tocci.ps.gz P. Kolm, P. Arbenz, and W. Gander Generalized Subspace Correction Methods kolm-arbenz-gander.abs kolm-arbenz-gander.ps.gz C.-Y. G. Lai Multilevel Solvers of First-Order System Least-Squares for Stokes Equations lai.abs lai.ps.gz A. A. Lorber, G. F. Carey, S. W. Bova, C. H. Harle Accelerated Solution of Non-Linear Navier-Stokes Problems using Chebyshev Iteration Polynomial Based Runge-Kutta Recursions lorber-carey-bova-harle.abs lorber-carey-bova-harle.ps.gz V. Menkov Solving Block Linear Systems with Low-Rank Off-Diagonal Blocks Is Easily Parallelizable menkov.abs menkov.ps.gz C. W. Oosterlee and T. Washio An Evaluation of Parallel Multigrid as Solver and Preconditioner for Singular Perturbation Problems oosterlee-washio.abs.ps.gz oosterlee-washio.ps.gz Y. Shapira Parallelizable Approximate Solvers for Recursions Arising in Preconditioning shapira.abs.ps.gz shapira.ps.gz M. Sosonkina, R. A. Kapania, H. F. Walker, and L. T. Watson A New Adaptive GMRES Algorithm for Achieving High Accuracy sosonkina-kapania-walker-watson.abs sosonkina-kapania-walker-watson.ps.gz S. V. Veronese and H. G. Othmer Scalable Implicit Methods for Reaction-Diffusion Equations in Two and Three Space Dimensions veronese-othmer.ps.gz K. Wu, Y. Saad, A. Strathopoulos Preconditioned Krylov Subspace Methods for Eigenvalue Problems wu-saad-strathopoulos.ps.gz D. Xie New Parallel SOR Method by Domain Partitioning xie.abs xie.ps.gz J. Zhang Multigrid Solution of the Convection-Diffusion Equation with High-Reynolds Number zhang.abs zhang.ps.gz ------------------------------------------------------- Date: Fri, 1 Mar 1996 20:53:28 -0700 From: jmandel@tiger.cudenver.edu (Jan Mandel) Subject: Some BibTeX Entries Editor's Note: These will eventually be in the bibliography (as they appear ------------- in publications), but not necessarily with the same key! @techreport{SGhosal_JMandel_RTezaur_1994tr, author = "S. Ghosal and J. Mandel and R. Tezaur", title = "Fast Neural Networks for Domain Decomposition in Finite Element Analysis", institution = "Center for Computational Mathematics, University of Colorado at Denver", address = "Denver, CO", type = "UCD/CCM Report", number = "23", year = "1994", note = "Submitted to SISC" } The solution of large finite element problems on distributed memory (even shared virtual memory) computers calls for efficient partitioning of large and unstructured 3-D meshes into submeshes such that computations can be distributed across processors. It is desired that resulting subdomains (submeshes) are approximately of same size, and the total number of interface nodes between adjacent subdomains is minimal. Two fine-grain scalable parallel algorithms are proposed employing neural network paradigms that can efficiently perform mesh partitioning for subsequent domain decomposition computations. New implementations are developed such that both the techniques have almost {\em linear complexity} with respect to the problem size for serial execution. These substructuring techniques compare favorably to the well-known recursive spectral bisection (RSB) method and simulated annealing-based partitioning algorithm. @unpublished{JMandel_RTezaur_CFarhat_1995unp, author = "J. Mandel and R. Tezaur and C. Farhat", title = "Optimal {L}agrange Multiplier Based Domain Decomposition Method for Plate Bending Problems", note = "SIAM J. Sci. Stat. Comp., submitted", year = "1995" } We present a new Lagrange multiplier based domain decomposition method for solving iteratively systems of equations arising from the finite element discretization of plate bending problems. The proposed method is essentially an extension of the FETI substructuring algorithm to the biharmonic equation. The main idea is to enforce the continuity of the transversal displacement field at the subdomain crosspoints throughout the p reconditioned conjugate gradient iterations. The resulting method is proved to have a condition number that does not grow with the number of subdomains, and grows at most polylogarithmically with the number of elements per subdomain. These optimal properties hold for numerous plate bending elements that are used in practice including the HCT, DKT, and a class of non-locking elements for the Reissner-Mindlin plate models. Computational experiments are reported and shown to confirm the theoretical opti mal convergence properties of the new domain decomposition method. Computational efficiency is a lso demonstrated with the numerical solution in 45 iterations and 105 seconds on a 64-processor IBM SP2 of a plate bending problem with almost one million degrees of freedom. @unpublished{JMandel_RTezaur_1994unp, author = "J. Mandel and R. Tezaur", title = "On the Convergence of a Substructuring Method with {L}agrange multipliers", note = "Numerische Mathematik, to appear" } We analyze the convergence of a substructuring iterative method with Lagrange multipliers, proposed recently by Farhat and Roux. The method decomposes finite element discretization of an elliptic boundary value problem into Neumann problems on the subdomains plus a coarse problem for the subdomain nullspace components. For linear conforming elements and preconditioning by the Dirichlet problems on the subdomains, we prove the asymptotic bound on the condition number $C (1+\log (H/h))^\gamma$, $\gamma=2$ or $3$,where $h$ is the characteristic element size and $H$ subdomain size. @incollection{PVanek_RTezaur_MBrezina_JKrizkova_1995a, author = "P. Van{\v e}k and R. Tezaur and M. Brezina and J. K{\v r}{\'i}{\v z}kov{\' a}", title = "Two--level method with coarse space size independent convergence", booktitle = "Domain Decomposition Methods in Sciences and Engineering", publisher = "John Wiley \& Sons Ltd.", address = "New York, N.Y.", editor = "R. Glowinski and J. P{\'e}riaux and Z. Shi and O. Widlund", year = "1995", note = "to appear", } We propose a nontraditional domain decomposition-type iterative method with the rate of convergence uniform with respect to coarse-space size. The method avoids a concept of local subdomain solvers and therefore is significantly less expensive than classical domain decomposition algorithms. @unpublished{RTezaur_PVanek_MBrezina_1996unp, author = "R. Tezaur and P. Van{\v e}k and M. Brezina", title = "Two-level method for solids on unstructured meshes", note = "SIAM J. Sci. Comp., submitted", year = "1996" } We propose an abstract two-level algorithm with convergence independent of the coarse-space size. The abstract algorithm is applied to problems of solids discretized on unstructured meshes. With no regularity assumptions we prove uniform convergence with respect to coarse-space size, domain, essential boundary conditions and jumps in Young modulus. Numerical experiments confirm the theory and show that the method works well even if some assumptions of the theory are violated. @article{SGhosal_PVanek_1995a, author = "S. Ghosal, P. Van{\v e}k", title = "A fast scalable algorithm for discontinuous optical flow estimation", journal = "IEEE Trans. Pattern Anal. Mach. Intel.", volume = "18", number = "2", year = "1996", pages = "181-195", } @article{PVanek_SGhosal_1995b, author = "P. Van{\v e}k and S. Ghosal", title = "A new technique for construction of image pyramids", journal = "Asian Conference on Computer Vision", volume = "1", year = "1996", pages = "479--483", } @unpublished{PLeTallec_JMandel_MVidrascu_1995unp, author = "P. {Le Tallec} and J. Mandel and M. Vidrascu", title = "A {N}eumann-{N}eumann domain decomposition algorithm for solving plate and shell problems", note = "SIAM J. Numer. Anal., submitted", } @inproceedings{PLeTallec_JMandel_MVidrascu_1994a, author = "P. {Le Tallec} and J. Mandel and M. Vidrascu", title = "Parallel domain decomposition algorithms for solving plate and shell problems", booktitle = "Advances in Parallel and Vector Processing for Structural Mechanics", editors = "B. H. V. Topping and M. Papadrakakis", publisher = "CIVIL-COMP Ltd", address = "Edinburgh", year = "1994", note = "Proceedings, Athens, 1994", } @unpublished{PVanek_JMandel_MBrezina_1995unp, author = "P. Van{\v e}k and J. Mandel and M. Brezina", title = "Algebraic multigrid based on smoothed aggregation for second and fourth order problems", note = "Computing, to appear", } @article{CFarhat_PSChen_JMandel_1995a, author = "C. Farhat and P. S. Chen and J. Mandel", title = "Scalable {L}agrange multiplier based domain decomposition method for time-dependent problems", journal = "Int. J. Numer. Meth. Engrg.", year = "1995", note = "To appear", } @unpublished{JMandel_1994unp, author = "J. Mandel", title = "Iterative methods for p-version finite elements: {P}reconditioning thin solids", institution = "Center for Computational Mathematics, University of Colorado at Denver", address = "Denver, CO", type = "UCD/CCM Report", number = "31", year = "1994", note = "J. Comput. Meth. Appl. Mech. Engrg., submitted", } @unpublished{JMandel_MBrezina_1994unp, author = "J. Mandel and M. Brezina", title = "Balancing Domain Decomposition for Problems with Large Jumps in Coefficients", note = "Mathematics of Computation, to appear", } ------------------------------ End of MGNet Digest **************************