Abstract
Domain decomposition by nested dissection for concurrent factorization and storage (CFS) of asymmetric matrices is coupled with finite element and spectral element discretizations and with Newton's method to yield an algorithm for parallel solution of nonlinear initial-and boundary-value problem. The efficiency of the CFS algorithm implemented on a MIMD computer is demonstrated by analysis of the solution of the two-dimensional, Poisson equation discretized using both finite and spectral elements. Computation rates and speedups for the LU-decomposition algorithm, which is the most time consuming portion of the solution algorithm, scale with the number of processors. The spectral element discretization with high-order interpolating polynomials yields especially high speedups because the ratio of communication to computation is lower than for low-order finite element discretizations. The robustness of the parallel implementation of the finite-element/Newton algorithm is demonstrated by solution of steady and transient natural convection in a two-dimensional cavity, a standard test problem for low Prandtl number convection. Time integration is performed using a fully implicit algorithm with a modified Newton's method for solution of nonlinear equations at each time step. The efficiency of the CFS version of the finite-element/Newton algorithm compares well with a spectral element algorithm implemented on a MIMD computer using iterative matrix methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ashcraft, C., Eisenstat, S., and Liu, J. (1990). A fan-in algorithm for distributed sparse numerical factorization.SIAM J. Sci. Statist. Comput. 11, 593–599.
Behnia, M., and de Vahl Davis, G. (1990). Fine mesh solutions using stream function-vorticity formulation. In Roux, B. (ed.),Numerical Simulation of Oscillatory Convection in Low-Pr Fluids, Braunschweig, Germany. Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, pp. 11–18.
Brown, R. A. (1988). Theory of transport processes in single crystal growth from the melt.AIChE 34(6), 881–911.
Carey, G. F., and Oden, J. T. (1986).Finite Elements, Vol. 6, Prentice Hall, Englewood Cliffs, New Jersey.
Dahlquist, G., Bjorck, A., and Anderson (Trans.), N. (1974).Numerical Methods. Prentice Hall, Englewood Cliffs, New Jersey.
Daube, O., and Rida, S. (1990). Contribution to the GAMM workshop. In Roux, B. (ed.),Numerical Simulation of Oscillatory Convection in Low-Pr Fluids, Braunschweig, Germany. Friedr. Vieweg & Sohn Verlagsgesellschaft mbH.
Finlayson, B. A. (1972).The Methods of Weighted Residuals and Variational Principles, with Application in Fluid Mechanics, Heat and Mass Transfer. Academic Press, New York.
Fischer, P. F. (1993). Personal communication.
Fischer, P. F., and Patera, A. T. (1994). Parallel simulation of viscous incompressible flows.Ann. Rev. Fluid Mech. 26, 483–527.
Gear, C. W. (1971).Numerical Initial Value Problems in Ordinary Differential Equations. Prentice-Hall, Englewood Cliffs, New Jersey.
George, A. (1973). Nested dissection of a regular finite element mesh.SIAM J. Numer. Anal. 10, 345–367.
George, A., Liu, J., and Ng, E. (1987). Communication reduction in parallel sparse Cholesky factorization on a hypercube. In Heath, M. (ed.),Hypercube Multiprocessors, Philadelphia, Pennsylvania Society for Industrial and Applied Mathematics, pp. 576–586.
George, A., and Liu, J. W. H. (1981).Computer Solution of Large Sparse Positive Definite Systems. Prentice Hall, Englewood Cliffs, New Jersey.
Golub, G. H., and Van Loan, C. F. (1989).Matrix Computations. The Johns Hopkins University Press, Baltimore, Maryland, Second edition.
Golub, G. H., and Welsch, J. H. (1969). Calculation of Gaussian quadrature rules.Mathematics of Computation 23, 221–230.
Gresho, P. M., Lee, R. L., and Sani, R. L. (1980). On the time-dependent solution of the incompressible Navier-Stokes equations in two and three dimensions. In Taylor, C., and Morgan, K. (eds.),Recent Advances in Numerical Methods in Fluids, Swansea, Pineridge, Volume 1, pp. 27–79.
Heath, M. T., Ng, E., and Peyton, B. W. (1991). Parallel algorithms for sparse linear systems.SIAM Review 33(3), 420–460.
Hendrickson, B., and Leland, R. (1993).The Chaco User's Guide. Sandia National Laboratories, Albuquerque, New Mexico 87185.
Ho, L. W., and Patera, A. T. (1990). A Legendre spectral element method for simulation of unsteady incompressible viscous free-surface flows.Computer Methods in Applied Mechanics and Engineering 80(1–3), 355–366.
Hood, P. (1976). Frontal solution program for unsymmetric matrices.J. Num. Meth. Engng. 10, 379–399.
Hood, P. (1977). Note on frontal solution program for unsymmetric matrices.J. Num. Meth. Engng. 11, 1055.
Hurle, D. T. J., Jakeman, E., and Johnson, C. P. (1974). Convective temperature oscillations in molten gallium.J. Fluid Mech. 64, 565–576.
Irons, B. M. (1970). A frontal solution program for finite element analysis.Int. J. Num. Meth. Engng. 2:5–32.
Keller, H. B. (1977). Numerical solution of bifurcation and nonlinear eigenvalue problems. In Rabinowitz, P. H. (ed.),Applications of Bifurcation Theory, New York, San Francisco, London. Academic Press, Inc., pp. 359–384.
Kuck (1992).CLASSPACK Basic Math Library, Kuck and Associates, Inc., Champaign, Illinois.
Lucas, R. F., Blank, T., and Tiemann, J. J. (1987). A parallel solution method for large sparse systems of equations.IEEE Trans. Computer-Aided Design CAD-6(6), 981–991.
Maday, Y., and Patera, A. T. (1989). Spectral element methods for the Navier-Stokes equations. In Noor, A. K., and Oden, J. T. (eds.),State-of-the-Art Surveys in Computational Mechanics, New York American Society of Mechanical Engineers, pp. 71–143.
Mehrabi, M. R. (1994). Modeling Transport Processes in Directional Solidification: I. Instabilities and Nonlinear Evolutions in Binary Alloys; II. Direct Parallel Solution of PDE's. Ph.D. thesis, MIT, Cambridge, Massachusetts.
Mehrabi, M. R., and Brown, R. A. (1993). An incomplete nested dissection algorithm for parallel solution of finite element discretizations of partial differential equations.J. Sci. Computing 8, 373–387.
Mu, M., and Rice, J. R. (1992). A grid-based subtree-subcube assignment strategy for solving partial differential equations on hypercubes.SIAM J. Sci. Stat. Comput. 13(3), 826–839.
Nekton (1991).Nekton User's Guide, Version 2.7. Nektonics, Inc., Cambridge, Massachusetts.
Patera, A. T. (1984). A spectral method for fluid dynamics, laminar flow in a channel expansion.J. Computl. Phys. 54(3):468–488.
Rønquist, E. M. (1988). Optimal Spectral Element Methods for the Navier-Stokes Equations. Ph.D. thesis, MIT, Cambridge, Massachusetts.
Roux, B. (ed.) (1990).Numerical Simulation of Oscillatory Convection in Low-Pr Fluids, Notes on Numerical Fluid Mechanics, Vol. 27, Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig, Germany.
Salinger, A. G., Xiao, Q., Zhou, Y., and Derby, J. J. (1993). Massively parallel finite element computations of three-dimensional, time-dependent, incompressible flows in materials processing systems. Submitted toComputl. Methods Appl. Mech. Engrg.
Tsiveriotis, K., and Brown, R. A. (1993). Solution of free-boundary problems using finite-element/Newton methods and locally refined grids: Application to analysis of solidification microstructure.Intl. J. Numer. Methods Fluids 16(9), 827–843.
Ungar, L. H., Ramprasad, N., and Brown, R. A. (1988). Finite element methods for unsteady solidification problems arising in prediction of morphological structure.J. Sci. Comp. 3, 77–108.
Winters, K. H. (1988). Oscillatory convection in liquid metals in a horizontal temperature gradient.Intl. J. Numer. Methods Engrng. 25, 401–414.
Yamaguchi, Y., Chang, C. J., and Brown, R. A. (1984). Multiple buoyancy-driven flows in a vertical cylinder heated from below.Phil. Trans. R. Soc. Lond. A312, 519–552.
Author information
Authors and Affiliations
Additional information
Submitted toJ. Scientific Computing, August 25, 1994.
Rights and permissions
About this article
Cite this article
Mehrabi, M.R., Brown, R.A. Parallel implementation of finite-element/newton method for solution of steady-state and transient nonlinear partial differential equations. J Sci Comput 10, 93–137 (1995). https://doi.org/10.1007/BF02087962
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02087962