Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “nested dissection”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1976

A variant of nested dissection for solving n by n grid problems

Nested dissection orderings are known to be very effective for solving the sparse positive definite linear systems which arise from n by n grid problems. In this paper nested dissection is shown to be the final step of incomplete nested dissection, an ordering which corresponds to the premature termination of dissection. Analyses of the arithmetic and storage requirements for incomplete nested dissection are given, and the ordering is shown to be competitive with nested dissection under certain conditions.

George, A.↗
NASA NTRS1978

Incomplete nested dissection for solving n by n grid problems

Nested dissection orderings are known to be very effective for solving sparse positive definite linear systems which arise from n by n grid problems. In this paper we consider incomplete nested dissection, an ordering which corresponds to the premature termination of nested dissection. Analyses of the arithmetic and storage requirements for incomplete nested dissection are given and the ordering is shown to be competitive with nested dissection with regard to arithmetic operations and superior to that ordering in storage requirements.

George, A.↗
NASA NTRS1992

Towards a fast implementation of spectral nested dissection

We describe the spectral nested dissection (SND) algorithm, a new algorithm for computing orderings appropriate for parallel factorization of sparse, symmetric matrices. The algorithm makes use of spectral properties of the Laplacian matrix associated with the given matrix to compute separators. We evaluate the quality of the spectral orderings with respect to several measures: fill, elimination tree height, height and weight balances of elimination trees, and clique tree heights. We use some very large structural analysis problems as test cases and demonstrate on these real applications (such as the Space Shuttle Solid Rocket Booster) that spectral orderings compare quite favorably with commonly used orderings, outperforming them by a wide margin for some of these measures. The only disadvantage of SND is its relatively long execution time. We will present some recent efforts to improve the execution time using both a multilevel and a hybrid approach. We use SND in computing a multifrontal numerical factorization with the different orderings on an eight processor Cray Y-MP and show its effectiveness. We believe that spectral nested dissection is a major breakthrough in terms of generating efficient sparse orderings for parallel machines.

Pothen, Alex↗
DOE OSTI2020

An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations

Here, we propose a new algorithm for the fast solution of large, sparse, symmetric positive-definite linear systems, spaND (sparsified Nested Dissection). It is based on nested dissection, sparsification, and low-rank compression. After eliminating all interiors at a given level of the elimination tree, the algorithm sparsifies all separators corresponding to the interiors. This operation reduces the size of the separators by eliminating some degrees of freedom but without introducing any fill-in. This is done at the expense of a small and controllable approximation error. The result is an approximate factorization that can be used as an efficient preconditioner. We then perform several numerical experiments to evaluate this algorithm. We demonstrate that a version using orthogonal factorization and block-diagonal scaling takes fewer CG iterations to converge than previous similar algorithms on various kinds of problems. Furthermore, this algorithm is provably guaranteed to never break down and the matrix stays symmetric positive-definite throughout the process. We evaluate the algorithm on some large problems show it exhibits near-linear scaling. The factorization time is roughly $\mathcal{O}$(N), and the number of iterations grows slowly with N.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1989

Communication requirements of sparse Cholesky factorization with nested dissection ordering

Load distribution schemes for minimizing the communication requirements of the Cholesky factorization of dense and sparse, symmetric, positive definite matrices on multiprocessor systems are presented. The total data traffic in factoring an n x n sparse symmetric positive definite matrix representing an n-vertex regular two-dimensional grid graph using n exp alpha, alpha not greater than 1, processors are shown to be O(n exp 1 + alpha/2). It is O(n), when n exp alpha, alpha not smaller than 1, processors are used. Under the conditions of uniform load distribution, these results are shown to be asymptotically optimal.

Naik, Vijay K.↗
DOE OSTI2022

Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks

We present a novel method for graph partitioning, based on reinforcement learning and graph convolutional neural networks. Our approach is to recursively partition coarser representations of a given graph. The neural network is implemented using SAGE graph convolution layers, and trained using an advantage actor critic (A2C) agent. We present two variants, one for finding an edge separator that minimizes the normalized cut or quotient cut, and one that finds a small vertex separator. The vertex separators are then used to construct a nested dissection ordering to permute a sparse matrix so that its triangular factorization will incur less fill-in. The partitioning quality is compared with partitions obtained using METIS and SCOTCH, and the nested dissection ordering is evaluated in the sparse solver SuperLU. Our results show that the proposed method achieves similar partitioning quality as METIS and SCOTCH. Furthermore, the method generalizes across different classes of graphs, and works well on a variety of graphs from the SuiteSparse sparse matrix collection.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1978

Analysis of dissection algorithms for vector computers

Recently two dissection algorithms (one-way and incomplete nested dissection) have been developed for solving the sparse positive definite linear systems arising from n by n grid problems. Concurrently, vector computers (such as the CDC STAR-100 and TI ASC) have been developed for large scientific applications. An analysis of the use of dissection algorithms on vector computers dictates that vectors of maximum length be utilized thereby implying little or no dissection; on the other hand, minimizing operation counts suggest that considerable dissection be performed. In this paper we discuss the resolution of this conflict by minimizing the total time required by vectorized versions of the two algorithms.

George, A.↗
NASA NTRS1995

Nonlinear structural analysis on distributed-memory computers

A computational strategy is presented for the nonlinear static and postbuckling analyses of large complex structures on massively parallel computers. The strategy is designed for distributed-memory, message-passing parallel computer systems. The key elements of the proposed strategy are: (1) a multiple-parameter reduced basis technique; (2) a nested dissection (or multilevel substructuring) ordering scheme; (3) parallel assembly of global matrices; and (4) a parallel sparse equation solver. The effectiveness of the strategy is assessed by applying it to thermo-mechanical postbuckling analyses of stiffened composite panels with cutouts, and nonlinear large-deflection analyses of HSCT models on Intel Paragon XP/S computers. The numerical studies presented demonstrate the advantages of nested dissection-based solvers over traditional skyline-based solvers on distributed memory machines.

Watson, Brian C.↗
NASA NTRS1995

Postbuckling and large-deflection nonlinear analyses on distributed-memory computers

A computational strategy is presented for postbuckling and nonlinear static analyses of large complex structures on distributed-memory parallel computers. The strategy is designed for message-passing parallel computer systems. The key elements of the proposed strategy are: (1) a multiple-parameter reduced basis technique; (2) a nested dissection (or multilevel substructuring) ordering scheme; (3) parallel assembly of global matrices; and (4) a parallel sparse equation solver. The effectiveness of the strategy is assessed by performing thermomechanical postbuckling analyses of stiffened composite panels with cutouts, and nonlinear large-deflection analyses of High Speed Civil Transport models on three distributed-memory computers. The numerical studies presented demonstrate the advantages of nested dissection-based solvers over traditional skyline-based solvers on distributed-memory machines.

Watson, Brian C.↗
NASA NTRS1985

Parallel solution of closely coupled systems

An odd-even permutation and a nested dissection technique were used to circumvent the strong seriality of a system of closely coupled equations. The effect of transforming the n x n Hermitian definite positive matrix coefficient on the topology of Cholesky factors is discussed. A series of directed graphs is constructed in order to show the computational steps required for the odd-even permutation. Numerical expressions for the speed-up and efficiency of parallel N-processing techniques and sequential processing by a single computer are derived. Similar expressions are derived for the case of insufficient processing capacity. The application of the odd-even permutation to the ensemble class of computer architectures is demonstrated.

Utku, S.↗
NASA NTRS1987

Solving very large, sparse linear systems on mesh-connected parallel computers

The implementation of Pan and Reif's Parallel Nested Dissection (PND) algorithm on mesh connected parallel computers is described. This is the first known algorithm that allows very large, sparse linear systems of equations to be solved efficiently in polylog time using a small number of processors. How the processor bound of PND can be matched to the number of processors available on a given parallel computer by slowing down the algorithm by constant factors is described. Also, for the important class of problems where G(A) is a grid graph, a unique memory mapping that reduces the inter-processor communication requirements of PND to those that can be executed on mesh connected parallel machines is detailed. A description of an implementation on the Goodyear Massively Parallel Processor (MPP), located at Goddard is given. Also, a detailed discussion of data mappings and performance issues is given.

Opsahl, Torstein↗
NASA NTRS1986

Parallel solution of closely coupled systems

The odd-even permutation and associated unitary transformations for reordering the matrix coefficient A are employed as means of breaking the strong seriality which is characteristic of closely coupled systems. The nested dissection technique is also reviewed, and the equivalence between reordering A and dissecting its network is established. The effect of transforming A with odd-even permutation on its topology and the topology of its Cholesky factors is discussed. This leads to the construction of directed graphs showing the computational steps required for factoring A, their precedence relationships and their sequential and concurrent assignment to the available processors. Expressions for the speed-up and efficiency of using N processors in parallel relative to the sequential use of a single processor are derived from the directed graph. Similar expressions are also derived when the number of available processors is fewer than required.

Utku, S.↗
NASA NTRS1988

Newton solution of inviscid and viscous problems

The application of Newton iteration to inviscid and viscous airfoil calculations is examined. Spatial discretization is performed using upwind differences with split fluxes. The system of linear equations which arises as a result of linearization in time is solved directly using either a banded matrix solver or a sparse matrix solver. In the latter case, the solver is used in conjunction with the nested dissection strategy, whose implementation for airfoil calculations is discussed. The boundary conditions are also implemented in a fully implicit manner, thus yielding quadratic convergence. Complexities such as the ordering of cell nodes and the use of a far field vortex to correct freestream for a lifting airfoil are addressed. Various methods to accelerate convergence and improve computational efficiency while using Newton iteration are discussed. Results are presented for inviscid, transonic nonlifting and lifting airfoils and also for laminar viscous cases.

Venkatakrishnan, V.↗
NASA NTRS1995

Sensitivity analysis for large-deflection and postbuckling responses on distributed-memory computers

A computational strategy is presented for calculating sensitivity coefficients for the nonlinear large-deflection and postbuckling responses of laminated composite structures on distributed-memory parallel computers. The strategy is applicable to any message-passing distributed computational environment. The key elements of the proposed strategy are: (1) a multiple-parameter reduced basis technique; (2) a parallel sparse equation solver based on a nested dissection (or multilevel substructuring) node ordering scheme; and (3) a multilevel parallel procedure for evaluating hierarchical sensitivity coefficients. The hierarchical sensitivity coefficients measure the sensitivity of the composite structure response to variations in three sets of interrelated parameters; namely, laminate, layer and micromechanical (fiber, matrix, and interface/interphase) parameters. The effectiveness of the strategy is assessed by performing hierarchical sensitivity analysis for the large-deflection and postbuckling responses of stiffened composite panels with cutouts on three distributed-memory computers. The panels are subjected to combined mechanical and thermal loads. The numerical studies presented demonstrate the advantages of the reduced basis technique for hierarchical sensitivity analysis on distributed-memory machines.

Watson, Brian C.↗
DOE OSTI2022

Small Mammal Prey Study for the Mexican Spotted Owl at Two Locations at Los Alamos National Laboratory

In New Mexico, Mexican spotted owls (Strix occidentalis lucida) are typically found in rocky canyons consisting of mixed-conifer forests that have experienced minimal human disturbance. At Los Alamos National Laboratory (LANL), Mexican spotted owls have been found breeding and foraging in habitats consistent with their known biology, but face the impact of human encroachment in the surrounding upland habitat. Little is known about the prey base present within the Laboratory’s vast forests. In anticipation of expanding human development in proximity to known occupied owl habitat, the goal of our study was to evaluate the small mammal prey base available to Mexican spotted owls at the Laboratory and to assess prey availability, diversity and composition. We sampled two study plots within the Laboratory’s forests for small mammals in 2021. Study plots were situated in conifer, deciduous, mixed conifer-deciduous and mixed oak. Our small mammal trapping efforts and SCR modeling revealed site-specific differences in prey base diversity, abundance and density between the unoccupied Pajarito Canyon and nearby occupied Mortandad Canyon site. These results highlight how managing tracts of land for small mammal prey base may overlap with goals set forth by researchers for Mexican spotted owl habitat needs. We recommend further trapping efforts to better understand prey availability in occupied and unoccupied sites at LANL as well as further investigation of prey selection through the dissection of pellets found in the areas surrounding known nesting locations.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2022

Simultaneous dissection of grain carotenoid levels and kernel color in biparental maize populations with yellow-to-orange grain

Maize enriched in provitamin A carotenoids could be key in combatting vitamin A deficiency in human populations relying on maize as a food staple. Consumer studies indicate that orange maize may be regarded as novel and preferred. This study identifies genes of relevance for grain carotenoid concentrations and kernel color, through simultaneous dissection of these traits in 10 families of the US maize nested association mapping panel that have yellow to orange grain. Quantitative trait loci were identified via joint-linkage analysis, with phenotypic variation explained for individual kernel color quantitative trait loci ranging from 2.4% to 17.5%. These quantitative trait loci were cross-analyzed with significant marker-trait associations in a genome-wide association study that utilized ~27 million variants. Nine genes were identified: four encoding activities upstream of the core carotenoid pathway, one at the pathway branchpoint, three within the α- or β-pathway branches, and one encoding a carotenoid cleavage dioxygenase. Of these, three exhibited significant pleiotropy between kernel color and one or more carotenoid traits. Kernel color exhibited moderate positive correlations with β-branch and total carotenoids and negligible correlations with α-branch carotenoids. These findings can be leveraged to simultaneously achieve desirable kernel color phenotypes and increase concentrations of provitamin A and other priority carotenoids.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2021

Genetic characterization of a Sorghum bicolor multiparent mapping population emphasizing carbon-partitioning dynamics

Sorghum bicolor, a photosynthetically efficient C4 grass, represents an important source of grain, forage, fermentable sugars, and cellulosic fibers that can be utilized in myriad applications ranging from bioenergy to bioindustrial feedstocks. Sorghum’s efficient fixation of carbon per unit time per unit area per unit input has led to its classification as a preferred biomass crop highlighted by its designation as an advanced biofuel by the U.S. Department of Energy. Due to its extensive genetic diversity and worldwide colonization, sorghum has considerable diversity for a range of phenotypes influencing productivity, composition, and sink/source dynamics. To dissect the genetic basis of these key traits, we present a sorghum carbon-partitioning nested association mapping (NAM) population generated by crossing 11 diverse founder lines with Grassl as the single recurrent female. By exploiting existing variation among cellulosic, forage, sweet, and grain sorghum carbon partitioning regimes, the sorghum carbon-partitioning NAM population will allow the identification of important biomass-associated traits, elucidate the genetic architecture underlying carbon partitioning and improve our understanding of the genetic determinants affecting unique phenotypes within Poaceae. We contrast this NAM population with an existing grain population generated using Tx430 as the recurrent female. Genotypic data are assessed for quality by examining variant density, nucleotide diversity, linkage decay, and are validated using pericarp and testa phenotypes to map known genes affecting these phenotypes. We release the 11-family NAM population along with corresponding genomic data for use in genetic, genomic, and agronomic studies with a focus on carbon-partitioning regimes.

multiparental populations↗