P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2008 by Taylor & Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number-13: 978-1-58488-672-3 (Hardcover) This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the conse- quences of their use. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www. copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC) 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 Dedication To our Families P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 Contents PartI TheoryandCodeDevelopment..............................1 1 BoundaryValueProblems............................................3 1.1 SingleEllipticEquation..........................................3 1.1.1 ClassicalFormulation.....................................3 1.1.2 VariationalFormulation...................................4 1.1.3 LinearAcousticsEquations ...............................5 1.1.4 AxisymmetricEllipticProblems ..........................8 1.2 LinearElasticity ................................................. 9 1.2.1 ElasticityinCylindricalCoordinates: AxisymmetricProblems..................................11 1.3 MaxwellEquations.............................................13 1.3.1 AxisymmetricMaxwellProblems........................16 1.4 ElasticityCoupledwithAcoustics...............................18 2 ExacthpSequences,Projection-BasedInterpolation, DeRhamDiagrams.................................................25 2.1 ExactPolynomialSequences ....................................26 2.1.1 Ne´de´lec’sTetrahedronoftheSecondType ...............27 2.1.2 Ne´de´lec’sHexahedronoftheFirstType ..................29 2.1.3 Ne´de´lec’sTetrahedronoftheFirstType ..................31 2.1.4 PrismaticElements......................................37 2.1.5 ParametricElements ....................................37 2.1.6 PyramidElements.......................................39 2.2 H1-, H(curl)-,and H(div)-ConformingProjection-Based Interpolation...................................................44 2.2.1 CommutingProjection-BasedInterpolationin1D.........44 2.2.2 CommutingProjection-BasedInterpolationin2D.........46 2.2.3 CommutingProjection-BasedInterpolationin3D.........47 2.2.4 Discussion...............................................48 2.3 ShapeFunctions................................................50 3 3DhpFiniteElementMethod.......................................61 3.1 ConstructionofFEBasisFunctionsonRegularMeshes..........61 3.2 Supportedh-Refinements.......................................65 3.2.1 h-RefinementAlgorithm.................................66 3.2.2 1-IrregularMeshesAlgorithm............................68 3.2.3 Modified1-IrregularMeshesAlgorithm..................72 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 3.3 p-RefinementsandtheMinimumRule..........................74 3.4 ConstrainedApproximation....................................75 3.4.1 NodesConstrainedbyanEdge..........................75 3.4.2 NodesConstrainedbyaFace............................76 3.4.3 ModifiedElement........................................78 4 3DhpCode..........................................................81 4.1 Organizationofthe3DhpCode .................................81 4.2 DataStructureinFORTRAN90 .................................82 4.3 DataStructureSupportingAlgorithms ......................... 84 4.3.1 NaturalOrderofElements ..............................84 4.3.2 DeterminingMiddleNodeNeighbors foraMid-FaceNode.....................................86 4.3.3 DeterminingMiddleNodeNeighbors foraMid-EdgeNode ....................................87 4.3.4 ReconstructingNodalConnectivities ....................88 5 GeometryModeling.................................................91 5.1 GMPManifold:CompatibleParametrizations...................92 5.2 TransfiniteInterpolation........................................94 5.2.1 TransfiniteInterpolationforaHexahedron...............94 5.2.2 TransfiniteInterpolationforaRectangleConforming toaSurface..............................................96 5.3 InterfacingwithCUBIT.........................................97 5.4 ExactGeometryandParametricElements:MeshGeneration...101 5.4.1 HowtoDefinetheFEError.............................102 6 Automatichp-AdaptivityinThreeSpaceDimensions..............105 6.1 ThehpAlgorithm..............................................105 6.1.1 Overview...............................................106 6.1.2 TheEdgeRefinementAlgorithm........................107 6.1.3 TheFaceRefinementAlgorithm.........................110 6.1.4 TheBrickRefinementAlgorithm........................113 6.1.5 MeshReconciliation....................................113 6.1.6 AbstractFrameworkforComputingProjections.........115 6.1.7 ThehpAlgorithmin H(curl)............................117 6.2 GoalOrientedhp-Adaptivity...................................117 6.2.1 DualProblemandErrorRepresentationFormula........118 6.2.2 TheGoalOrientedhp-Algorithm........................120 6.3 Examples......................................................122 6.3.1 Fichera’sCorner........................................122 6.3.2 AManufacturedSolutionwithaShock..................124 6.3.3 ElectromagneticScatteringinaWaveguide..............128 P1:BinayaDash September19,2007 13:33 C6722 C6722˙C000 7 High-PerformanceComputation...................................135 7.1 FastIntegrationAlgorithm.....................................135 7.2 TelescopicSolver..............................................140 7.2.1 TheSymmetricPositive-DefiniteCase...................140 7.2.2 TheSymmetricIndefiniteCase..........................143 7.3 LinearSolvers.................................................146 7.3.1 TheSymmetricPositive-DefiniteCase...................147 7.3.2 ADomainDecompositionSolverforAcoustics andElectromagnetics...................................149 8 Two-GridhpSolver................................................153 8.1 Formulation...................................................154 8.1.1 OverlappingBlock-JacobiSmoother ....................154 8.1.1.1 Block-JacobiSmootherforElectromagnetic Problems.......................................156 8.1.1.2 SpeciallyDesignedBlocksforElongated Elements.......................................158 8.1.2 Coarse-GridCorrection.................................159 8.1.3 Krylov-SubspaceOptimizationMethods ................160 8.1.4 TheTwo-GridAlgorithm...............................163 8.1.5 StoppingCriterion......................................164 8.2 ElementaryConvergenceTheory..............................164 8.2.1 EllipticSymmetricandPositive-DefiniteProblems.......164 8.2.1.1 ConvergencePropertiesofSmoothing Iterations......................................164 8.2.1.2 ConvergencePropertiesofTwo-GridSolver Iterations......................................165 8.2.2 ElectromagneticProblem...............................166 8.2.2.1 EquivalencebetweenElectromagnetics andanAuxiliarySymmetricandPositive- DefiniteProblem...............................168 8.2.2.2 ConvergenceforSymmetricandPositive- DefiniteAuxiliaryProblem.....................170 8.3 ImplementationDetails........................................172 8.3.1 Block-JacobiSmoother..................................172 8.3.2 StiffnessMatrix.........................................173 8.3.3 CoarseGridCorrectionandProlongation/Restriction Operators..............................................173 8.3.4 EmbeddingGradientsof H1into H(curl) forElectromagneticProblems...........................174 8.3.5 KrylovSubspaceOptimizationMethods................175 8.4 NumericalExamples..........................................176 8.4.1 ModelProblems........................................178 8.4.2 Goal-OrientedTwo-GridSolver.........................178