Abstracts of SPC/SFB-preprints, 1993-96 (very) incomplete list ----------------------------------------------------------------- spc94_4.dvi.Z, spc94_4.ps.Z --- NEW: spc95_20.ps.gz =================================================== aktualisierte Version von (SPC 93_1) Bibliotheken zur Entwicklung paralleler Algorithmen Gundolf Haase, Thomas Hommel, Arnd Meyer, Matthias Pester Fakult"at f"ur Mathematik Technische Universit"at Chemnitz-Zwickau Reichenhainer Str. 41 D-09107 Chemnitz, FRG The purpose of this paper is to supply a summary of library subroutines and functions for parallel MIMD computers. The subroutines have been developed at the University of Chemnitz during a period of the last five years. In detail, they are concerned with vector operations, inter-processor communication and simple graphic output to workstations. One of the most valuable features is the machine-independence of the communication subroutines proposed in this paper for a hypercube topology of the parallel processors (excepting a kernel of only two primitive system-dependend operations). They were implemented and tested for different hardware and operating systems including transputer, nCube, KSR, PVM. The vector subroutines are optimized by the use of C language and enrolled loops (BLAS1-like). The paper includes hints for using the libraries with both Fortran and C programs. (in German) (50 pages) ----------------------------------------------------------------- spc93_2.ps.Z ============= A Parallel Version of the Preconditioned Conjugate Gradient Method for Boundary Element Equations Matthias Pester Fachbereich Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG Sergej Rjasanow Institut f"ur Technomathematik Universit"at Kaiserslautern PSF 3042 D-67653 Kaiserslautern, FRG The parallel version of precondition techniques is developed for matrices arising from the Galerkin boundary element method for two-dimensional domains with Dirichlet boundary conditions. Results were obtained for implementations on a transputer network as well as on an nCUBE-2 parallel computer showing that iterative solution methods are very well suited for a MIMD computer. A comparison of numerical results for iterative and direct solution methods is presented and underlines the superiority of iterative methods for large systems. (16 pages) ----------------------------------------------------------------- spc93_3.dvi.Z spc93_3_0.ps.Z -- spc_93_3_7.ps.Z =============================================== PARMESH - a parallel mesh generator Gerhard Globisch Fachbereich Mathematik Technische Universit"at Chemnitz-Zwickau Reichenhainer Str. 41 D-09107 Chemnitz, FRG We developed a program for the automatically parallel triangular mesh generation in arbitrary bounded plane domains that are a- priori divided up into several single connected subdomains. Its output data structure briefly described too is very suitably for further performing parallel hierarchical mesh generation in each subdomain starting from the triangulation got there as well as for parallel processing itself. Two numerical examples are presented. Consequently this program package called PARMESH can be an efficient ingredient for parallel numerical solvers of discrete problems arisen from mathematical physics. (in English) (29 pages) ----------------------------------------------------------------- spc94_1.dvi.Z, spc94_1.ps.Z =========================== Efficient Time Step Parallelization of Full-Multigrid Techniques Joerg Weickert, Torsten Steidten Fachbereich Mathematik Technische Universit"at Chemnitz-Zwickau 09107 Chemnitz, FRG This paper deals with parallelization methods for time-dependent problems where the time steps are shared out among the processors. A Full Multigrid technique serves as solution algorithm, hence information of the preceding time step and of the coarser grid is necessary to compute the solution at each new grid level. Applying the usual extrapolation formula to process this information, the parallelization will not be very efficient. We developed another extrapolation technique which causes a much higher parallelization effect. Test examples show that no essential loss of exactness appears, such that the method presented here shall be well-applicable. (in English) (8 pages) ----------------------------------------------------------------- spc94_6.dvi.Z, spc94_6.ps.Z =========================== On an automatically parallel generation technique for tetrahedral meshes Gerhard Globisch Fachbereich Mathematik Technische Universit"at Chemnitz-Zwickau Reichenhainer Str. 41 D-09107 Chemnitz, FRG In order to prepare modern finite element analysis a program for the efficient parallel generation of tetrahedral meshes in a wide class of three dimensional domains having a generalized cylindric shape is presented. The applied mesh generation strategy is based on the decomposition of some 2D-reference domain into single con- nected subdomains by means of its triangulations the tetrahedral layers are built up in parallel. Adaptive grid controlling as well as nodal renumbering algorithms are involved. In the paper several examples are incorporated to demonstrate both program's capabilities and the handling with. (in English) (23 pages) ----------------------------------------------------------------- spc94_7.ps.Z ============ Tau-extrapolation - Theoretical foundations, numerical experiment and application to Navier-Stokes equations Klaus Bernert Fakult"at f"ur Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG The paper deals with tau-extrapolation - a modification of the multigrid method, which leads to solutions with an improved con- vergence order. The number of numerical operations depends linearly on the problem size and is not much higher than for a multigrid method without this modification. The paper starts with a short mathematical foundation of the tau-extrapolation. Then follows a careful tuning of some multigrid components necessary for a successful application of tau-extrapolation. The next part of the paper presents numerical illustrations to the theoretical investigations for one- dimensional test problems. Finally some experience with the use of tau-extrapolation for the Navier-Stokes equations is given. (24 pages) ----------------------------------------------------------------- spc94_12.dvi.Z, spc94_12.ps.Z ============================= Verarbeitung von Sparse-Matrizen in Kompaktspeicherform (KLZ/KZU) Arnd Meyer, Matthias Pester Fakult"at f"ur Mathematik Technische Universit"at Chemnitz-Zwickau Reichenhainer Str. 41 D-09107 Chemnitz, FRG The paper describes a storage scheme for sparse symmetric or nonsymmetric matrices which has been developed and used for many years at the Technical University of Chemnitz. An overview of existing library subroutines using such matrices is included. (in German) (16 pages) ----------------------------------------------------------------- spc94_15.ps.Z ============= Realization and comparison of various mesh refinement strategies near edges Thomas Apel Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz email: apel@mathematik.tu-chemnitz.de Frank Milde Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Physik D-09107 Chemnitz email: milde@physik.tu-chemnitz.de This paper is concerned with mesh refinement techniques for treating elliptic boundary value problems in domains with re- entrant edges and corners, and focuses on numerical experiments. After a section about the model problem and discretization strategies, their realization in the experimental code FEMPS3D is described. For two representative examples the numerically determined error norms are recorded, and various mesh refinement strategies are compared. The paper appeared as Preprint SPC 94_15, DFG-Forschergruppe SPC, TU Chemnitz, August 1994. ----------------------------------------------------------------- spc94_16.ps.Z ============= Elliptic problems in domains with edges: anisotropic regularity and anisotropic finite element meshes Thomas Apel Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz email: apel@mathematik.tu-chemnitz.de Serge Nicaise Universit\'e de Valenciennes et du Hainaut Cambr\'esis LIMAV and URA D 751 CNRS ``GAT'' Institut des Sciences et Techniques de Valenciennes B.P. 311 F--59304 - Valenciennes Cedex, France e-mail: snicaise@univ-valenciennes.fr This paper is concerned with the anisotropic singular behaviour of the solution of elliptic boundary value problems near edges. The paper deals first with the description of the analytic properties of the solution in newly defined, anisotropically weighted Sobolev spaces. The finite element method with anisotropic, graded meshes and piecewise linear shape functions is then investigated for such problems; the schemes exhibit optimal convergence rates with decreasing mesh size. For the proof, new local interpolation error estimates in anisotropically weighted spaces are derived. Moreover, it is shown that the condition number of the stiffness matrix is not affected by the mesh grading. Finally, a numerical experiment is described, that shows a good agreement of the calculated approximation orders with the theoretically predicted ones. The paper appeared as Preprint SPC 94_16, DFG-Forschergruppe SPC, TU Chemnitz, August 1994. It is submitted to SIAM J. Numer. Anal. ----------------------------------------------------------------- spc94_18.ps.Z ============= A parallel preconditioned iterative realization of the panel method in 3D Matthias Pester Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz, FRG Sergej Rjasanow Institut f"ur Technomathematik Universit"at Kaiserslautern PSF 3042 D-67653 Kaiserslautern, FRG The parallel version of precondition iterative techniques is developed for matrices arising from the panel boundary element method for three-dimensional simple connected domains with Dirichlet boundary conditions. Results were obtained on an nCUBE-2 parallel computer showing that iterative solution methods are very well suited also in three-dimensional case for implementation on a MIMD computer and that they are much more efficient than usual direct solution techniques. (16 pages) ----------------------------------------------------------------- spc94_23.ps.Z ============= On-Lline visualization in parallel computations Matthias Pester Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik Reichenhainer Str. 41 D-09107 Chemnitz, FRG The investigation of new parallel algorithms for MIMD computers requires some postprocessing facilities for quickly evaluating the behavior of those algorithms We present two kinds of visualization tool implementations for 2D and 3D finite element applications to be used on a parallel computer and a host workstation. (in English) (9 pages +3) ----------------------------------------------------------------- spc94_24.ps.Z ============= Grafik-Ausgabe vom Parallelrechner f"ur 2D-Gebiete Matthias Pester Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik Reichenhainer Str. 41 D-09107 Chemnitz, FRG The paper mainly describes the user interface of some graphical visualization tools for parallel finite element applications in 2D (layer problems, deformation problems, fluid dynamics). There are presented some examples of various methods to display the numerical results. (in German) (16 pages) ----------------------------------------------------------------- spc94_26.ps.Z ============= Local inequalities for anisotropic finite elements and their application to convection-diffusion problems Thomas Apel Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz email: apel@mathematik.tu-chemnitz.de Gert Lube Georg-August-Universt"at G"ottingen Fachbereich Mathematik Institut f"ur Numerische und Angewandte Mathematik Lotzestr.~16--18 D-37083 G"ottingen email: lube@namu01.gwdg.de The paper gives an overview over local inequalities for anisotropic simplicial Lagrangian finite elements. The main original contributions are the estimates for higher derivatives of the interpolation error, the formulation of the assumptions on admissible anisotropic finite elements in terms of geometrical conditions in the three-dimensional case, and an anisotropic variant of the inverse inequality. An application of anisotropic meshes in the context of a stabilized Galerkin method for a convection-diffusion problem is given. --------------------------------------------------------------------------- spc95_1.ps.Z ============ Anisotropic mesh refinement in stabilized Galerkin methods Thomas Apel Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz email: apel@mathematik.tu-chemnitz.de Gert Lube Georg-August-Universt"at G"ottingen Fachbereich Mathematik Institut f"ur Numerische und Angewandte Mathematik Lotzestr. 16-18 D-37083 G"ottingen email: lube@namu01.gwdg.de The numerical solution of the convection-diffusion-reaction problem is considered in two and three dimensions. A stabilized finite element method of Galerkin/Least squares type accomodates diffusion-dominated as well as convection- and/or reaction- dominated situations. The resolution of boundary layers occuring in the singularly perturbed case is accomplished using anisotropic mesh refinement in boundary layer regions. In this paper, the standard analysis of the stabilized Galerkin method on isotropic meshes is extended to more general meshes with boundary layer refinement. Simplicial Lagrangian elements of arbitrary order are used. --------------------------------------------------------------------------- spc95_4.ps.Z ============= Grafik-Ausgabe vom Parallelrechner f"ur 3D-Gebiete Magdalene Meyer Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik Reichenhainer Str. 41 D-09107 Chemnitz, FRG The paper describes a method for Visualization of computational results in parallel finite element applications for 3D problems. The visualization itself is done on a workstation using a post- processing tool based on GRAPE, which interacts with the parallel program to obtain data. (in German) (12 pages) ----------------------------------------------------------------- spc95_5.ps.Z ============ Parallel solution of finite element equation systems: efficient inter-processor communication Thomas Apel Technische Universit"at Chemnitz-Zwickau Arnd Meyer Fakult"at f"ur Mathematik Matthias Pester D-09107 Chemnitz Gundolf Haase Johannes Kepler Universit"at Linz Institut f"ur Mathematik Altenbergerstr. 69 A-4040 Linz e-mail: apel@mathematik.tu-chemnitz.de ghaase@miraculix.numa.uni-Linz.ac.at a.meyer@mathematik.tu-chemnitz.de mspester@mathematik.tu-chemnitz.de This paper deals with the application of domain decomposition methods for the parallel solution of boundary value problems for partial differential equations over a domain $Omegabset R^d$, $d=2,3$. The attention is focused on the conception of efficient communication routines for the data exchange which is necessary for example in the preconditioned cg-algorithm for solving the resulting system of algebraic equations. The paper describes the data structure, different algorithms, and computational tests. --------------------------------------------------------------------------- --------------------------------------------------------------------------- SFB393/96-08: ============= Navier-Stokes equations as a differential-algebraic system J"org Weickert Technische Universit"at Chemnitz-Zwickau Fakult"at f"ur Mathematik D-09107 Chemnitz Nonsteady Navier-Stokes equations represent a differential-algebraic system of strangeness index one after any spatial discretization. Since such systems are hard to treat in their original form, most approaches use some kind of index reduction. Processing this index reduction it is important to take care of the manifolds contained in the differential-algebraic equation (DAE). We investigate for several discretization schemes for the Navier-Stokes equations how the consideration of the manifolds is taken into account and propose a variant of solving these equations along the lines of the theoretically best index reduction. Applying this technique, the error of the time discretisation depends only on the method applied for solving the DAE. --------------------------------------------------------------------------- SFB393/96-12 ============ Scalability, Efficiency, and Robustness of Parallel Multilevel Solvers for Nonlinear Equations Bodo Heise Institut f"ur Mathematik Johannes Kepler Universit"at Linz Altenberger Strasse 69 A - 4040 Linz Michael Jung Fakult"at f"ur Mathematik Technische Universit"at Chemnitz-Zwickau D - 09107 Chemnitz e-mail: heise@numa.uni-linz.ac.at michael.jung@mathematik.tu-chemnitz.de In this paper we compare the performance, scalability, and robustness of different parallel algorithms for the numerical solution of nonlinear boundary value problems arising in the magnetic field computation and in solid mechanics. These problems are discretized by using the finite element method with triangular meshes and piecewise linear functions. The nonlinearity is handled by a nested Newton solver, and the linear systems of algebraic equations within each Newton step are solved by means of various iterative solvers, namely multigrid methods and conjugate gradient methods with preconditioners based on domain decomposition, multigrid, or BPX techniques, respectively. The basis of the implementation of all solvers is a non-overlapping domain decomposition data structure such that they are well-suited for parallel machines with MIMD architecture. --------------------------------------------------------------------------- SFB393/96-21 ============ Two-point boundary value problems with piecewise constant coefficients: weak solution and exact discretization G"unther Windisch Fakult"at f"ur Mathematik Technische Universit"at Chemnitz-Zwickau D - 09107 Chemnitz For two-point boundary value problems in weak formulation with piecewise constant coefficients and piecewise continuous right-hand side functions we derive a representation of its weak solution by local Green's functions. Then we use it to generate exact three-point discretizations by Galerkin's method on essentially arbitrary grids. The coarsest possible grid is the set of points at which the piecewise constant coefficients and the right- hand side functions are discontinuous. This grid can be refined to resolve any solution properties like boundary and interior layers much more correctly. The proper basis functions for the Galerkin method are entirely defined by the local Green's functions. The exact discretizations are of completely exponentially fitted type and stable. The system matrices of the resulting tridiagonal systems of linear equations are in any case irreducible M-matrices with a uniformly bounded norm of its inverse. ------------------------------------------------------------------- sfb97-01.dvi.gz, sfb97-01.ps.gz =============================== A new method for computing the stable invariant subspace of a real Hamiltonian matrix or Breaking Van Loan's curse? Peter Benner Zentrum fuer Technomathematik Fachbereich 3/Mathematik und Informatik Postfach 330440 D-28334 Bremen, FRG e-mail: benner@numerik.uni-bremen.de Volker Mehrmann Fakult"at f"ur Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG e-mail: mehrmann@mathematik.tu-chemnitz.de Hongguo Xu Department of Mathematics Fudan University Shanghai 200433, PR China Current address: Fakult"at f"ur Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG e-mail: hxu@mathematik.tu-chemnitz.de. Preprint-Reihe des Chemnitzer SFB 393 `Numerische Simulation auf massiv parallelen Rechnern', SFB 393/97-01, January 1997 Abstract. A new backward stable, structure preserving method of complexity O(n^3) is presented for computing the stable invariant subspace of a real Hamiltonian matrix and the stabilizing solution of the continuous-time algebraic Riccati equation. The new method is based on the relationship between the invariant subspaces of the Hamiltonian matrix H and the extended matrix /0 H\ and makes use \H 0/ of the symplectic URV-like decomposition that was recently introduced by the authors. ------------------------------------------------------------------- sfb97-02.dvi.gz sfb97-02.ps.gz ============================== RANK-REVEALING "TOP-DOWN" ULV FACTORIZATIONS Brahim Benhammouda Fakult"at f"ur Mathematik TU Chemnitz-Zwickau D-09107 Chemnitz, FRG e-mail: brahim@mathematik.tu-chemnitz.de Preprint-Reihe des Chemnitzer SFB 393 `Numerische Simulation auf massiv parallelen Rechnern', SFB 393/97-02, January 1997 Abstract. Rank-revealing ULV and URV factorizations are useful tools to determine the rank and to compute bases for null-spaces of a matrix. However, in the practical ULV (resp. URV ) factorization each left (resp. right) null vector is recomputed from its corresponding right (resp. left) null vector via triangular solves. Triangular solves are required at initial factorization, refinement and updating. As a result, algorithms based on these factorizations may be expensive, especially on parallel computers where triangular solves are expensive. In this paper we propose an alternative approach. Our new rank-revealing ULV factorization, which we call "top-down" ULV factorization ( TDULV -factorization) is based on right null vectors of lower triangular matrices and therefore no triangular solves are required. Right null vectors are easy to estimate accurately using condition estimators such as incremental condition estimator (ICE). The TDULV factorization is shown to be equivalent to the URV factorization with the advantage of circumventing triangular solves. --------------------------------------------------------------------------- SFB393/96-22 ============ Variable Preconditioning Procedures for Elliptic Problems Michael Jung Faculty for Mathematics Technical University of Chemnitz-Zwickau D - 09107 Chemnitz, Germany Sergei V. Nepomnyaschikh Computing Center Siberian Branch of Russian Academy of Sciences Novosibirsk, 630090, Russia e-mail: michael.jung@mathematik.tu-chemnitz.de svnep@oapmg.sscc.ru For solving systems of grid equations approximating elliptic boundary value problems a method of constructing variable preconditioning procedures is presented. The main purpose is to discuss how an efficient preconditioning iterative procedure can be constructed in the case of elliptic problems with disproportional coefficients, e.g.~equations with a large coefficient in the reaction term (or a small diffusion coefficient). The optimality of the suggested technique is based on fictitious space and multilevel decom- position methods. Using an additive form of the preconditioners, we intro- duce factors into the preconditioners to optimize the corresponding conver- gence rate. The optimization with respect to these factors is used at each step of the iterative process. The application of this technique to two-level $p$-hierarchical precondi- tioners and domain decomposition methods is considered too. --------------------------------------------------------------------------- SFB393/97-16 ============ Error estimation for anisotropic tetrahedral and triangular finite element meshes. Gerd Kunert Faculty for Mathematics Technical University of Chemnitz-Zwickau D - 09107 Chemnitz, Germany e-mail: gerd.kunert@mathematik.tu-chemnitz.de Some boundary value problems yield anisotropic solutions, e.g.~solutions with boundary layers. If such problems are to be solved with the finite element method (FEM), anisotropically refined meshes can be advantageous. In order to construct these meshes or to control the error one aims at reliable error estimators. For \emph{isotropic} meshes many estimators are known, but they either fail when used on \emph{anisotropic} meshes, or they were not applied yet. For rectangular (or cuboidal) anisotropic meshes a modified error estimator had already been found. We are investigating error estimators on anisotropic tetrahedral or triangular meshes because such grids offer greater geometrical flexibility. For the Poisson equation a residual error estimator, a local Dirichlet problem error estimator, and an $L_2$ error estimator are derived, respectively. Additionally a residual error estimator is presented for a singularly perturbed reaction diffusion equation. It is important that the anisotropic mesh corresponds to the anisotropic solution. Provided that a certain condition is satisfied, we have proven that all estimators bound the error reliably. Keywords: finite elements, error estimator, anisotropic solution, stretched elements, tetrahedral mesh, singularly perturbed problem AMS(MOS): 65N30, 65N15, 35B25 --------------------------------------------------------------------------- SFB393/97-27 ============ Graph Partitioning: A Survey Ulrich Elsner Faculty for Mathematics Technical University of Chemnitz-Zwickau D - 09107 Chemnitz, Germany e-mail: elsner@mathematik.tu-chemnitz.de Many problems appearing in scientific computing and other areas can be formulated as a graph partitioning problems. Examples include data distribution for parallel computers, decomposition of sparse matrices and VLSI-design. In this survey we present the graph partitioning problem, describe some applications and introduce many of the algorithms used to solve the problem. Keywords: graph partitioning, graph bisection, mesh partitioning, mesh bisection, spectal bisection, recursive bisection, inertial bisection, multilevel graph partitioning, multilevel bisection AMS: 05C85 Graph theory; Graph algorithms 05C50 Graph theory; Graphs and matrices 68R10 Discrete math. in relation to computer science; Graph theory 94C15 Circuits, networks; Applications of graph theory 65F50 Numerical linear algebra; Sparse Matrices ---------------------------------------------------------------------------