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: file://na.cs.yale.edu/pub/mgnet/www/mgnet.html or http://www.cerfacs.fr Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 4, Number 10 (approximately October 31, 1994) Today's topics: European MGNet Mirror and Re-organization of the Archives Meisdorf Meeting Abstracts Call for papers (Computing special issue) Time Parallel Paper Paper on Nonnested Space Multilevel Methods Bib Items for MGNet from Tony Chan ------------------------------------------------------- Date: Mon, 31 Oct 1994 09:39:49 GMT From: douglas@cerfacs.fr Subject: European MGNet Mirror and Re-organization of the Archives CERFACS now has a mirror of MGNet. It is currently available through Mosaic with the URL name of http://www.cerfacs.fr It will be available later this week by anonymous ftp (ftp.cerfacs.fr). Hopefully, people in Europe will be able to access this easier than the repository at Yale. I took this opportunity to re-organize where some things are stored on MGNet. For example, I moved all of the software packages from the top level directory to a new subdirectory called Codes. The new organization is as follows: Codes All software packages are stored in subdirectories in here. Conferences Information, abstracts, or papers from old conferences are stored in here. For example, CopperMtn93 has the proceedings from the April, 1993 Copper Mountain meeting in it. How2Submit.mgnet A short summary of commands that can be used to put something into the archives using ftp. INDEX.mgnet A summary of what is in the archives (and where). README Simple information to get started. Whois Who receives the digests by e-mail (to the best of my knowledge). bib The 2,000+ BibTeX database. conferences Announcements of future meetings. digests The old digests (all of them). incoming Where new things get put before being stored in the right place (only at Yale, not the mirror sites). papers Where lots of preprints are stored. There are some other files and directories, but they are only for operating MGNet. ------------------------------------------------------- Date: Mon, 17 Oct 1994 18:36:11 +0200 (MESZ) From: Friedhelm SchieweckSubject: Meisdorf Meeting Abstracts Concerning the abstracts I have to say that only a part of them (27) is available on the computer (as LaTeX), the other part exists only as a paper. Please tell me if you are intersted in this LaTeX-part of the abstracts which I could send you by ftp and if yes please tell me the directory on the server. Best regards, Friedhelm Editor's Note: Now in mgnet/Conferences/Meisdorf94. The incomplete set ------------- is in COLLECTION.dvi. Individual ones are in the Abstracts subdirectory. ------------------------------------------------------- Date: Wed, 26 Oct 1994 13:25:09 +0100 From: Annemarie Joehnk Subject: Call for papers (Computing special issue) Dear Mr Douglas, please post this call for papers at the appropriate place. Sincerely yours W. Hackbusch Call for Papers The journal COMPUTING is planning a special issue devoted to the subject of adaptive techniques. Special topics may, e.g., be - adaption techniques - grid refinement (isotropic, anisotropic, etc) - grid coarsening - error estimators - implementational details - adaptions of discretisations - treatment of different time-scales. The papers should be sent to the address below (or to any other editor of COMPUTING) until December 15, 1994. The "instructions to authors" are in every issue of COMPUTING (2 copies with summary, AMS subject classification, keywords, if possible German translation of the title and summary). The paper is to be sent to Prof Dr Wolfgang Hackbusch Editor of Computing Institut f"ur Informatik und Praktische Mathematik Christian-Albrechts-Universit"at D-24098 Kiel Germany Fax.++431-880 4054 e-mail: wh@informatik.uni-kiel.d400.de Please forward this information to interested colleagues. ------------------------------------------------------- Date: Sun, 2 Oct 94 14:09:57 MET From: Graham Horton Subject: Time Parallel Paper Here is a "time-parallel" method that will appear in sisc next year. A SPACE-TIME MULTIGRID METHOD FOR PARABOLIC PDES G. HORTON and S. VANDEWALLE Abstract We consider the solution of parabolic partial differential equations. In standard time- stepping techniques multigrid can be used as an iterative solver for the elliptic equations arising at each discrete time-step. By contrast, the method presented in this paper treats the whole of the space-time problem simultaneously. Thus the multigrid operations of smoothing and coarse grid correction are defined on all of the space-time variables of a given grid-level. The method is characterized by a coarsening strategy with prolongation and restriction operators which depend at each grid level on the degree of anisotropy of the discretization stencil. Numerical results for the one- and two-dimensional heat equation are presented and are shown to agree closely with predictions from Fourier mode analysis. Editor's Note: in mgnet/papers/Horton-Vandewalle/space-time.ps. ------------- ------------------------------------------------------- Date: Thu, 20 Oct 1994 17:06:40 GMT From: douglas@cerfacs.fr Subject: Paper on Nonnested Space Multilevel Methods A Unified Multigrid Theory for Non-Nested Grids and/or Quadrature C. C. Douglas, J. Douglas, Jr., and D. E. Fyfe In this paper, we extend some results from an earlier paper (SIAM J. Numer. Anal., 30 (1993), pp. 136-158) of the first two authors. We provide a unified theory for multilevel and multigrid methods when the usual assumptions are not present. For example, we do not assume that the solution spaces or the grids are nested. Further, we do not assume that there is an algebraic relationship between the linear algebra problems on different levels. What we provide is a computationally useful theory for adaptively changing levels. Theory is provided for multilevel correction schemes, nested iteration schemes, and one way (i.e., coarse to fine grid with no correction iterations) schemes. We include examples showing the applicability of this theory: finite element examples using quadrature in the matrix assembly and finite volume examples with non-nested grids. Our theory applies directly to finite difference, wavelet, and collocation based multilevel examples as well. (To appear in the East-West Journal of Numerical Mathematics, 1995.) Editor's Note: in mgnet/papers/Douglas-Douglas-Fyfe/nonnested.dvi. ------------- ------------------------------------------------------- Date: Wed, 2 Nov 1994 14:03:27 +0800 (EAT) From: Prof. Tony Chan Subject: Bib Items for MGNet from Tony Chan Craig, I promised you some bibitems for MGNet. Here they are. Sorry that not all of them are in bibtex format. Tony Editor's Note: These will appear in mgnet/bib/mgnet.bib sometime in early ------------- November. Thanks. \begin{enumerate} \item {\it Domain Decomposition Algorithms,} Tony F Chan and Tarek Mathew, Acta Numerica, Cambridge Univ. Press, 1994, pp. 61-143. \item {\it Templates for the solution of linear systems: Building blocks for iterative methods}, with R. Barrett et al, SIAM, Philadelphia, 1994 (book). \item {\it Scientific Computation}, Tony F Chan and Zhong-ci Shi (Eds), Proceedings of International Conference on Scientific Computation, Hangzhou, China, 20-23 August 1991, Series on Applied Mathematics, Vol. 1, World Scientific Press, 1992. \item {\it The interface probing technique in domain decomposition}, Tony F Chan and T. Mathew, SIAM J. Matrix Anal. Appl., 13, 1992, 212-238. \item {\it On the relationship between overlapping and nonoverlapping domain decomposition methods}, Tony F Chan and D. Goovaerts, SIAM J. Matrix Anal. Appl., 13, 1992, 663-670. \item {\it Multilevel filtering elliptic preconditioner}, C.C.J. Kuo, Tony F Chan and C. Tong, SIAM J. Sci. Stat. Comp., 11, 1990, 403-429. \item {\it Hierarchical Algorithms and Architectures for Parallel Scientific Computing}, Tony F Chan, invited paper in Proceedings of the ACM International Conference on Supercomputing, pp. 318-329, Amsterdam, The Netherlands, June 1990. \item {\it Geometry-Independent Convergence Results for Domain Decomposition Algorithms,} with Thomas Hou and P.L. Lions, %UCLA CAM Report 89-11, May 1989. SIAM J. Numer. Anal., Vol. 28, No.2, pp. 378-391, April 1991. \item {\it Parallel Elliptic Preconditioners: Fourier Analysis and Performance on the Connection Machine}, Tony F Chan, Jay Kuo and Charles Tong, Computer Physics Communicatins 53 (1989) 237-252. \item {\it Fourier Analysis of Preconditioned Iterative Methods}, Tony F Chan and Howard Elman, SIAM Review, Vol. 31, No. 1, pp. 20-49, March 1989. \item {\it The alternating-block-factorization procedure for systems of partial differential equations}, R.E. Bank, T.F. Chan, W.M. Coughran and R.K. Smith, BIT, 29, 1989, 938-954. %\item {\it Domain Decomposition Methods}, %Proceedings of the Second International %Symposium on Domain Decomposition Methods, UCLA, January 1988. %T.F. Chan, R. Glowinski, J. Periaux, O. Widlund (Eds.), %SIAM, Philadelphia, 1989. \item {\it FLO52 on hypercubes: performance of a parallel code for the Euler equations on hypercubes}, E. Barszcz, T.F. Chan, D.C. Jespersen, R.S. Tuminaro, J. High Speed Comp., 1, 1989, 481-503. \item {\it Analysis of preconditioners for domain decomposition} Tony F Chan, SIAM J. Numer. Anal., 24, 1987, 382-390. \item {\it Multigrid Algorithms on the Hypercube Multiprocessor}, Tony F Chan and Youcef Saad, IEEE Trans. Computers, Vol. C-35, No. 11, Nov. 1986, pp.969-977. \item {\it PLTMGC: A multigrid continuation program package for solving parametrized nonlinear elliptic systems}, SIAM J. Sci. Stat. Comp., 7, 1986, 540-559. \item {\it Analysis of projection methods for solving linear systems with multiple right-hand-sides}, with W.L. Wan, UCLA CAM Report 94-26, August 1994. \item {\it Multigrid and domain decomposition methods for unstructured meshes}, with B. Smith and J. Zou. In Proc. of the 3rd Int'l Conf. on Advances in Numerical Methods and Applications, Sofia, Bulgaria, August 1994, World Scientific, Singapore, pp. 53-62. \item {\it Parallel complexity of domain decomposition methods and optimal coarse grid size}, UCLA CAM Report 94-15, June 1994. \item {\it The composite step family of nonsymmetric conjugate gradient methods}, with Tedd Szeto, UCLA CAM Report 94-11, April 1994. In Proc. of PCG'94, Keio Univ., Yokahama, Japan. T. Nodera (ed.), Keio Univ. Press, 1994. \item {\it Overlapping Schwarz Methods on Unstructured Meshes Using Non-Matching Coarse Grids,} with Barry Smith and Jun Zou, UCLA CAM report 94-8, March 1994. \item {\it A sign cut version of the recursive spectral bisection graph partitioning algorithm}, with W.K. Szeto. UCLA CAM Report 94-7, March 1994. In Proc. SIAM Conf. Numer. Lin. Alg., Snowbird, Utah, June 1994. \item {\it Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes}, with Barry Smith. UCLA CAM Report 93-42, Dec. 93. To appear in Elec. Trans. Numer. Anal. \item {\it Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes}, with Jun Zou. UCLA CAM Report 93-40, Dec. 93. To appear in Numer. Algorithms. \item {\it A composite step conjugate gradient squared algorithm for solving nonsymmetric linear systems}, with Tedd Szeto, UCLA CAM Report 93-27, July 1993. Numer. Alg., vol. 7, no. 1, 1994, pp. 17-32. \item {\it Optimal coarse grid size in domain decomposition}, with J.P. Shao, UCLA CAM Report 93-24, July 1993. To appear in J. Comp. Math. \item {\it A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems}, with Randy Bank, UCLA CAM Report 93-21, June 1993. Numer. Alg., vol. 7, no. 1, 1994, pp. 1-16. \item {\it On the optimality of the median cut spectral bisection graph partitioning method}, UCLA CAM Report 93-14, June 1993. \item {\it Performance modelling for high order finite difference methods on the Connection Machine CM-2}, with Y.C. Chang. UCLA CAM Report 93-04, March 1993. To appear in J. Supercomputer and Applic. \item {\it An analysis of the composite step bi-conjugate gradient method}, with Randy Bank, Numer. Math., 66, 1993, 295-319. \item {\it Domain decomposition preconditioners for convection diffusion problems}, with Tarek Mathew. UCLA CAM Report 92-43, Oct. 1992. In Proc. of 6th Int'l Conf. on Domain Decomposition, A. Quarternoni et al (eds.), AMS, Providence, 1994. \item {\it A framework for block ILU factorizations using block-size reduction}, with P. Vassilevski. UCLA CAM Report 92-29, June 1992. To appear in Math. Comp. \item {\it QMRCGSTAB: A quasi-minimal residual variant of the Bi-CGSTAB algorithm for nonsymmetric systems}, with E. Gallopoulos, V. Simoncini, T. Szeto and C. Tong. SIAM J. Sci. Comp., 15, 1993, 338-347. %UCLA CAM Report 92-26, June 92. \end{enumerate} ======================================= @TECHREPORT{chan-mathew-shao-vs, AUTHOR="Tony F. Chan and Tarek P. Mathew and Jian Ping Shao", TITLE="Efficient Variants of the Vertex Space Domain Decomposition Algorithm", INSTITUTION="Department of Mathematics, UCLA ", YEAR="1992 ", NOTE="To appear in SIAM J. Sci. Comp.", NUMBER=" CAM 92-07 " } @PROCEEDINGS{dom2, TITLE="Domain Decomposition Methods ", EDITOR="Tony Chan and Roland Glowinski and and Jacques P{\'e}riaux and Olof Widlund", YEAR="1989", NOTE="Proceedings of the {S}econd {I}nternational {S}ymposium on {D}omain {D}ecomposition {M}ethods , {L}os {A}ngeles, {C}alifornia , January 14 - 16, 1988.", PUBLISHER="SIAM", ADDRESS="Philadelphia"} @PROCEEDINGS{dom3, TITLE="Domain Decomposition Methods ", EDITOR="Tony Chan and Roland Glowinski and and Jacques P{\'e}riaux and Olof Widlund", YEAR="1990", NOTE="Proceedings of the {T}hird {I}nternational {S}ymposium on {D}omain {D}ecomposition {M}ethods , {H}oston, {T}exas, 1989.", PUBLISHER="SIAM", ADDRESS="Philadelphia"} @PROCEEDINGS{dom4, TITLE="Domain Decomposition Methods ", EDITOR="Tony Chan and Roland Glowinski and and Jacques P{\'e}riaux and Olof Widlund", YEAR="1991", NOTE="Proceedings of the {F}ourth {I}nternational {S}ymposium on {D}omain {D}ecomposition {M}ethods , {M}oscow, {U}SSR, 1990.", PUBLISHER="SIAM", ADDRESS="Philadelphia"} @PROCEEDINGS{dom5, TITLE="Domain Decomposition Methods For Partial Differential Equations", EDITOR="David E. Keyes and Tony F. Chan and Gerard Meurant and Jeffrey S. Scroggs and Robert G. Voigt", YEAR="1992", NOTE="Proceedings of the {F}ifth {I}nternational {S}ymposium on {D}omain {D}ecomposition {M}ethods , {N}orfolk, USA, 1991.", PUBLISHER="SIAM", ADDRESS="Philadelphia"} @techreport{chan-dePillis-vandervorst, author={T.F. Chan and L. de Pillis and H.A. Van der Vorst}, title="A transpose-free squared Lanczos algorithm and application to solving nonsymmetric linear systems", number="CAM 91-17", institution="UCLA, Dept. of Math., Los Angeles, CA 90024-1555", year={1991}} @book{templates-94, author={R. Barrett and M. Berry and T.F. Chan and J. Demmel and J. Donato and J. Dongarra and V. Eijkhout and R. Pozo and C. Romine and H. van der Vorst}, title={Templates for the solution of linear systems: building blocks for iterative methods}, publisher={SIAM, Philadelphia}, year={1994}} @techreport{chan-meurant-fourier-block, author={T.F. Chan and G. Meurant}, title={Fourier analysis of block preconditioners}, institution={Dept. of Math., UCLA, Los Angeles}, number={CAM 90-04}, year={1990}} @article{chan-vassilevski-92, author={T.F. Chan and P. Vassilevski}, title={A framework for block {ILU} factorizations using block size reduction}, journal={Math. Comp.}, note={to appear}, year={1994}} @inproceedings{chan-hierarchical-90, author={T.F. Chan}, title={Hierarchical algorithms and architectures for parallel scientific computing}, booktitle={Proc. ACM Int'l Conf. Supercomputing, Amsterdam, The Netherlands}, pages={318-329}, year={1990}} @article{chan-kuo-tong-cm2, author={T.F. Chan and Jay C.C. Kuo and C.H. Tong}, title={Parallel elliptic preconditioners: Fourier analysis and performance on the {C}onnection {M}achine}, journal={Comp. Phys. Commun.}, pages={237-252}, volume={53}, year={1989}} @phdthesis{tong-thesis-90, author={C.H. Tong}, title={Parallel preconditioned conjugate gradient methods for elliptic partial differential equations}, year={1990}, school={Dept. of Comp. Sci., Univ. of Calif. at Los Angeles}} @article{kuo-chan-rb-90, author={J.C.C. Kuo and T.F. Chan}, title={Two-color Fourier analysis of iterative algorithms for elliptic problems with red/black ordering}, journal={SIAM J. Sci. Stat. Comp.}, year={1990}, pages={767-793}, volume={11}} @inproceedings{tong-cm-89, author={C.H. Tong}, title={The preconditioned conjugate gradient method on the {C}onnection {M}achine}, booktitle={Scientific application of the Connection Machine}, editor={H. Simon}, publisher={World Scientific}, pages={188-213},year={1989}} @article{chan-goovaert-ddilu-90, author={T.F. Chan and D. Goovaerts}, title={A note on the efficiency of domain decomposed incomplete factorizations}, journal={SIAM J. Sci. Stat. Comp.}, volume={11}, number={4}, pages={794-803}, year={1990}} @article{chan-rilu-91, author={T.F. Chan}, title={Fourier analysis of relaxed incomplete factorization preconditioners}, journal={SIAM J. Sci. Stat. Comp.}, volume={12}, pages={668-680}, year={1991}} @phdthesis{donato-thesis-91, author={J.M. Donato}, title={Iterative methods for scalar and coupled systems of elliptic equations}, school={Dept. of Math., Univ. Calif. at Los Angeles}, year={1991}} @techreport{ChRe:survey85, author={T.F. Chan and D. Resasco}, title={A survey of preconditioners for domain decomposition}, institution={Dept. of Comp. Sci., Yale Univ.}, number={DCS/RR-414}, year={1985}} @article{ChMa:probe92, author={T.F. Chan and T. Mathew}, title={The interface probing technique in domain decomposition}, journal={SIAM J. Matrix Anal. Applic.}, volume={13}, number={1}, year={1992}, pages={212-238}} ------------------------------ End of MGNet Digest **************************