# Direct methods for sparse matrices

IntroductionGraph theoryExample of a sparse matrixModern computer architecturesComputational performanceProblem formulationSparse matrix test collectionsExercisesSPARSE MATRICES: STORAGE SCHEMES AND SIMPLE OPERATIONSIntroductionSparse vector storageInner product of two packed vectorsAdding packed vectorsUse of full-sized arraysCoordinate scheme for storing sparse matricesSparse matrix as a collection of sparse vectorsSherman’s compressed index schemeLinked listsSparse matrix in column-linked listSorting algorithmsThe counting sortHeap sortTransforming the coordinate scheme to other formsAccess by rows and columnsSupervariablesMatrix by vector productsMatrix by matrix productsPermutation matricesClique (or finite-element) storageComparisons between sparse matrix structuresExercisesGAUSSIAN ELIMINATION FOR DENSE MATRICES: THE ALGEBRAIC PROBLEMIntroductionSolution of triangular systemsGaussian eliminationRequired row interchangesRelationship with LU factorizationDealing with interchangesLU factorization of a rectangular matrixComputational sequences, including blockingSymmetric matricesMultiple right-hand sides and inversesComputational costPartitioned factorizationSolution of block triangular systemsExercisesGAUSSIAN ELIMINATION FOR DENSE MATRICES: NUMERICAL CONSIDERATIONSIntroductionComputer arithmetic errorAlgorithm instabilityControlling algorithm stability through pivotingPartial pivotingThreshold pivotingRook pivotingFull pivotingThe choice of pivoting strategyOrthogonal factorizationPartitioned factorizationMonitoring the stabilitySpecial stability considerationsSolving indefinite symmetric systemsIll-conditioning: introductionIll-conditioning: theoretical discussionIll-conditioning: automatic detectionThe LINPACK condition estimatorHager’s methodIterative refinementScalingAutomatic scalingScaling so that all entries are close to oneScaling normsI-matrix scalingExercisesResearch exercisesIntroductionNumerical stability in sparse Gaussian eliminationTrade-offs between numerical stability and sparsityIncorporating rook pivotingx 2 pivotingOther stability considerationsEstimating condition numbers in sparse computationOrderingsBlock triangular matrixLocal pivot strategiesBand and variable band orderingDissectionFeatures of a code for the solution of sparse equationsInput of dataThe ANALYSE phaseThe FACTORIZE phaseThe SOLVE phaseOutput of data and analysis of resultsRelative work required by each phaseMultiple right-hand sidesComputation of entries of the inverseMatrices with complex entriesWriting compared with using sparse matrix softwareExercisesREDUCTION TO BLOCK TRIANGULAR FORMIntroductionFinding the block triangular form in three stagesLooking for row and column singletonsFinding a transversalBackgroundTransversal extension by depth-first searchAnalysis of the depth-first search transversal algorithmImplementation of the transversal algorithmSymmetric permutations to block triangular formBackgroundThe algorithm of Sargent and WesterbergTarjan’s algorithmImplementation of Tarjan’s algorithmEssential uniqueness of the block triangular formExperience with block triangular formsMaximum transversalsWeighted matchingsThe Dulmage—Mendelsohn decompositionExercisesResearch exerciseLOCAL PIVOTAL STRATEGIES FOR SPARSE MATRICESIntroductionThe Markowitz criterionMinimum degree (Tinney scheme 2)A priori column orderingSimpler strategiesA more ambitious strategy: minimum fill-inEffect of tie-breaking on the minimum degree algorithmNumerical pivotingSparsity in the right-hand side and partial solutionVariability-type orderingThe symmetric indefinite caseExercisesResearch exercisesORDERING SPARSE MATRICES FOR BAND SOLUTIONIntroductionBand and variable-band matricesSmall bandwidth and profile: Cuthill—McKee algorithmSmall bandwidth and profile: the starting nodeSmall bandwidth and profile: Sloan algorithmSpectral ordering for small profileCalculating the Fiedler vectorHybrid orderings for small bandwidth and profileHager’s exchange methods for profile reductionBlocking the entries of a symmetric variable-band matrixRefined quotient treesIncorporating numerical pivotingThe fixed bandwidth caseThe variable bandwidth caseConclusionExercisesORDERINGS BASED ON DISSECTIONIntroductionOne-way dissectionFinding the dissection cuts for one-way dissectionNested dissectionIntroduction to finding dissection cutsMultisectionComparing nested dissection with minimum degreeEdge and vertex separatorsMethods for obtaining dissection setsObtaining an initial separator setRefining the separator setGraph partitioning algorithms and softwareDissection techniques for unsymmetric systemsBackgroundGraphs for unsymmetric matricesOrdering to singly bordered block diagonal formThe performance of the orderingSome concluding remarksExercisesResearch exerciseIMPLEMENTING GAUSSIAN ELIMINATION WITHOUT SYMBOLIC FACTORIZEIntroductionMarkowitz ANALYSEFACTORIZE without pivotingFACTORIZE with pivotingSOLVEHyper-sparsity and linear programmingSwitching to full formLoop-free codeInterpretative codeThe use of drop tolerances to preserve sparsityExploitation of parallelismVarious parallelization opportunitiesParallelizing the local ordering and sparse factorization stepsExercisesIMPLEMENTING GAUSSIAN ELIMINATION WITH SYMBOLIC FACTORIZEIntroductionMinimum degree orderingApproximate minimum degree orderingDissection orderingsNumerical FACTORIZE using static data structuresNumerical pivoting within static data structuresBand methodsVariable-band (profile) methodsFrontal methods: introductionFrontal methods: SPD finite-element problemsFrontal methods: general finite-element problemsFrontal methods for non-element problemsExploitation of parallelismExercisesResearch exerciseGAUSSIAN ELIMINATION USING TREESIntroductionMultifrontal methods for finite-element problemsElimination and assembly treesThe elimination treeUsing the assembly tree for factorizationThe efficient generation of elimination treesConstructing the sparsity pattern of UThe patterns of data movementManipulations on assembly treesOrdering of childrenTree rotationsNode amalgamationMultifrontal methods: symmetric indefinite problemsExercisesGRAPHS FOR SYMMETRIC AND UNSYMMETRIC MATRICESIntroductionSymbolic analysis on unsymmetric systemsNumerical pivoting using dynamic data structuresStatic pivotingScaling and reorderingThe aims of scalingScaling and reordering a symmetric matrixThe effect of scalingDiscussion of scaling strategiesSupernodal techniques using assembly treesDirected acyclic graphsParallel issuesParallel factorizationParallelization levelsThe balance between tree and node parallelismUse of memoryStatic and dynamic mappingStatic mapping and schedulingDynamic schedulingCodes for shared and distributed memory computersThe use of low-rank matrices in the factorizationUsing rectangular frontal matrices with local pivotingTrees for unsymmetric matricesExercisesResearch exercisesTHE SOLVE PHASEIntroductionSOLVE at the node levelUse of the tree by the SOLVE phaseSparse right-hand sidesMultiple right-hand sidesComputation of null-space basisParallelization of SOLVEParallelization of dense solveOrder of access to the tree nodesExperimental resultsExercisesResearch exerciseOTHER SPARSITY-ORIENTED ISSUESIntroductionThe matrix modification formulaThe basic formulaThe stability of the matrix modification formulaApplications of the matrix modification formulaApplication to stability correctionsBuilding a large problem from subproblemsComparison with partitioningApplication to sensitivity analysisThe model and the matrixModel reductionModel reduction with a regular submodelSparsity constrained backward error analysisWhy the inverse of a sparse irreducible matrix is denseComputing entries of the inverse of a sparse matrixSparsity in nonlinear computationsEstimating a sparse Jacobian matrixUpdating a sparse Hessian matrixApproximating a sparse matrix by a positive-definite oneSolution methods based on orthogonalizationHybrid methodsDomain decompositionBlock iterative methodsExercisesResearch exercises