SEARCH · Search NASA

Results for “Laplacian”

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.

SourceResearch connectionFrom yearThrough year

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

At least 73 records · Page 4

All sources NASA NTRS DOE OSTI

DOE OSTI2023

Graph Sparsification by Approximate matrix Multiplication

Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of sparsifying a weighted graph, while sharing the same vertices as the original graph but reducing the number of edges, is through spectral sparsification. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians, without requiring spectral information. Through the CR–MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Here, we define a new notion of additive spectral sparsifiers, which has not been considered in the literature.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Learning Optimal Multigrid Smoothers via Neural Networks

Multigrid methods are one of the most efficient techniques for solving large sparse linear systems arising from partial differential equations (PDEs) and graph Laplacians from machine learning applications. One of the key components of multigrid is smoothing, which aims at reducing high-frequency errors on each grid level. However, finding optimal smoothing algorithms is problem-dependent and can impose challenges for many problems. In this paper, we propose an efficient adaptive framework for learning optimized smoothers from operator stencils in the form of convolutional neural networks (CNNs). Here, the CNNs are trained on small-scale problems from a given type of PDEs based on a supervised loss function derived from multigrid convergence theories and can be applied to large-scale problems of the same class of PDEs. Numerical results on anisotropic rotated Laplacian problems and variable coefficient diffusion problems demonstrate improved convergence rates and solution time compared with classical hand-crafted relaxation methods.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Towards a Unified theory of Fractional and Nonlocal Vector Calculus

Nonlocal and fractional-order models capture effects that classical partial differential equations cannot describe; for this reason, they are suitable for a broad class of engineering and scientific applications that feature multiscale or anomalous behavior. This has driven a desire for a vector calculus that includes nonlocal and fractional gradient, divergence and Laplacian type operators, as well as tools such as Green’s identities, to model subsurface transport, turbulence, and conservation laws. In the literature, several independent definitions and theories of nonlocal and fractional vector calculus have been put forward. Some have been studied rigorously and in depth, while others have been introduced ad-hoc for specific applications. The goal of this work is to provide foundations for a unified vector calculus by (1) consolidating fractional vector calculus as a special case of nonlocal vector calculus, (2) relating unweighted and weighted Laplacian operators by introducing an equivalence kernel, and (3) proving a form of Green’s identity to unify the corresponding variational frameworks for the resulting nonlocal volume-constrained problems. Here, the proposed framework goes beyond the analysis of nonlocal equations by supporting new model discovery, establishing theory and interpretation for a broad class of operators, and providing useful analogues of standard tools from the classical vector calculus.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

A Unified Theory of Fractional Nonlocal and Weighted Nonlocal Vector Calculus

Nonlocal and fractional-order models capture effects that classical partial differential equations cannot describe; for this reason, they are suitable for a broad class of engineering and scientific applications that feature multiscale or anomalous behavior. This has driven a desire for a vector calculus that includes nonlocal and fractional gradient, divergence and Laplacian type operators, as well as tools such as Green's identities, to model subsurface transport, turbulence, and conservation laws. In the literature, several independent definitions and theories of nonlocal and fractional vector calculus have been put forward. Some have been studied rigorously and in depth, while others have been introduced ad-hoc for specific applications. The goal of this work is to provide foundations for a unified vector calculus by (1) consolidating fractional vector calculus as a special case of nonlocal vector calculus, (2) relating unweighted and weighted Laplacian operators by introducing an equivalence kernel, and (3) proving a form of Green's identity to unify the corresponding variational frameworks for the resulting nonlocal volume-constrained problems. The proposed framework goes beyond the analysis of nonlocal equations by supporting new model discovery, establishing theory and interpretation for a broad class of operators, and providing useful analogues of standard tools from the classical vector calculus.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1982

High spatial resolution Mg/Al maps of the western Crisium and Sulpicius Gallus regions

High spatial resolution Mg/Al ratio maps of the western Crisium and Sulpicius Gallus regions of the moon are presented. The data is from the X-ray fluorescence experiment and the image enhancement technique in the Laplacian subtraction method using a special least-squares version of the Laplacian to reduce noise amplification. In the highlands region west of Mare Crisium several relatively small patches of smooth material have high local Mg/Al ratio similar to values found in mare sites, suggesting volcanism in the highlands. In the same highland region there were other smooth areas with no high Mg/Al local values and they are probably Cayley Formation material produced by impact mass wasting. The Sulpicius Gallus region has variable Mg/Al ratios. In this region there are several high Mg/Al ratio spots, two of which occur at the highland-mare interface. Another high Mg/Al ratio area corresponds to the Sulpicius Gallus Rima I region. The high Mg/Al ratio material in the Sulpicius Gallus region is probably pyroclastic.

Schonfeld, E.↗

NASA NTRS1988

Discretization formulas for unstructured grids

The Galerkin weighted residual technique using linear triangular weight functions is employed to develop finite difference formula in cartesian coordinates for the Laplacian operator, first derivative operators and the function for unstructured triangular grids. The weighted residual coefficients associated with the weak formulation of the Laplacian operator are shown to agree with the Taylor series approach on a global average. In addition, a simple algorithm is presented to determine the Voronoi (finite difference) area of an unstructured grid.

Baumeister, Kenneth J.↗

NASA NTRS1989

A finite difference treatment of Stokes-type flows: Preliminary report

The equations Laplacian operator omega = 0, (1.1a) and omega = Laplacian operator Chi, (1.1b) describe, in suitable units, 2-D Stokes flow of an incompressible fluid occupying a domain D in which omega is the vorticity and Chi is the stream function. The flow is uniquely determined by specifying the velocity on the boundary B of D, a condition which leads to specifying the stream function Chi and its normal derivative Chi sub n on B. A mathematically similar problem arises in describing the equilibrium of a flat plate in structural mechanics where a related 1-D problem by finite difference or finite element methods is to introduce effective methods for imposing the boundary conditions through which (1.1a) is coupled to (1.1b). These models thus provide a simple starting point for examining the general treatment of boundary conditions for more general time dependent Navier-Stokes incompressible flows. For the purpose of discussion it is assumed that D is a square domain. A standard finite difference method to solve (1.1) is to introduce a uniform grid and then use standard five point finite difference operators to express each equation in (1.1). At any point on the boundary B a value of Chi is specified by the boundary conditions but a value of omega at the same boundary mesh point will also be required to complete the computation. Methods are discussed which overcome the difficulty in solving these problems.

Rose, M. E.↗

NASA NTRS1988

Discretization formulas for unstructured grids

Baumeister, Kenneth J.↗

NASA NTRS1991

Numerical aspects of computing high Reynolds number flows on unstructured meshes

An edge-data structure describing a mesh edge-wise given the vertices of each edge and neighboring cell information is used developing algorithms for the Navier-Stokes equations on triangular meshes. Edge formulas for the Galerkin and finite-element discretization of gradient, divergence, Hessian, and Laplacian operators are derived. A simple edge formula is derived for the discretization of the Laplacian operator, where precise theoretical conditions for a discrete maximum principle can be ascertained. Practical issues associated with solving the Navier-Stokes equations on unstructured meshes are addressed, along with issues concerning the generation of highly stretched triangular meshes and the modeling of turbulence on unstructured meshes. A turbulence modeling strategy is proposed, and numerical results for a high-Reynolds-number flow about single- and multielement airfoils are discussed.

Barth, Timothy J.↗

NASA NTRS1993

On the optimality of a universal noiseless coder

Rice developed a universal noiseless coding structure that provides efficient performance over an extremely broad range of source entropy. This is accomplished by adaptively selecting the best of several easily implemented variable length coding algorithms. Variations of such noiseless coders have been used in many NASA applications. Custom VLSI coder and decoder modules capable of processing over 50 million samples per second have been fabricated and tested. In this study, the first of the code options used in this module development is shown to be equivalent to a class of Huffman code under the Humblet condition, for source symbol sets having a Laplacian distribution. Except for the default option, other options are shown to be equivalent to the Huffman codes of a modified Laplacian symbol set, at specified symbol entropy values. Simulation results are obtained on actual aerial imagery over a wide entropy range, and they confirm the optimality of the scheme. Comparison with other known techniques are performed on several widely used images and the results further validate the coder's optimality.

Yeh, Pen-Shu↗

NASA NTRS1994

An analysis of spectral envelope-reduction via quadratic assignment problems

A new spectral algorithm for reordering a sparse symmetric matrix to reduce its envelope size was described. The ordering is computed by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. In this paper, we provide an analysis of the spectral envelope reduction algorithm. We described related 1- and 2-sum problems; the former is related to the envelope size, while the latter is related to an upper bound on the work involved in an envelope Cholesky factorization scheme. We formulate the latter two problems as quadratic assignment problems, and then study the 2-sum problem in more detail. We obtain lower bounds on the 2-sum by considering a projected quadratic assignment problem, and then show that finding a permutation matrix closest to an orthogonal matrix attaining one of the lower bounds justifies the spectral envelope reduction algorithm. The lower bound on the 2-sum is seen to be tight for reasonably 'uniform' finite element meshes. We also obtain asymptotically tight lower bounds for the envelope size for certain classes of meshes.

George, Alan↗

NASA NTRS1993

A spectral algorithm for envelope reduction of sparse matrices

A new algorithm for reducing the envelope of a sparse matrix is presented. This algorithm is based on the computation of eigenvectors of the Laplacian matrix associated with the graph of the sparse matrix. A reordering of the sparse matrix is determined based on the numerical values of the entries of an eigenvector of the Laplacian matrix. Numerical results show that the new reordering algorithm can in some cases reduce the envelope by more than a factor of two over the current standard algorithms such as Gibbs-Poole-Stockmeyer (GPS) or SPARSPAK's reverse Cuthill-McKee (RCM).

Barnard, Stephen T.↗

NASA NTRS1994

Cluster growth modeling of plateau erosion

The pattern of erosion of a plateau along an escarpment may be modeled usng cluster growth techniques, recently popularized in models of drainage network evolution. If erosion on the scarp takes place in discrete events at rates subject to local substrate strength, the whole range of behavior is described by a combination of three cluster growth mechanisms: invasion percolation, Eden growth and diffusion-limited aggregation (DLA). These model the relative importance of preexisting substrate strength, background weathering, and seepage weathering and erosion respectively. The rate of seepage processes is determined by the efflux of groundwater at the plateau margin, which in turn is determined by the pressure field in the plateau aquifer. If this process acted alone, it would produce erosion patterns in the form of Laplacian fractals, with groundwater recharge from a distant source, or Poissionian fractals, with groundwater recharge uniform over the plateau. DLA is used to mimic the Laplacian or Poissonian potential field and the corresponding seepage growth process. The scaling structure of clusters grown by pure DLA, invasion percolation, or Eden growth is well known; this study presents a model which combines all three growth mechanisms for the first time. Mixed growth processes create clusters with different scaling properties and morphologies over distinct length scale ranges, and this is demonstrable in natural examples of plateau erosion.

Stark, Colin P.↗

NASA NTRS1995

Model-based VQ for image data archival, retrieval and distribution

An ideal image compression technique for image data archival, retrieval and distribution would be one with the asymmetrical computational requirements of Vector Quantization (VQ), but without the complications arising from VQ codebooks. Codebook generation and maintenance are stumbling blocks which have limited the use of VQ as a practical image compression algorithm. Model-based VQ (MVQ), a variant of VQ described here, has the computational properties of VQ but does not require explicit codebooks. The codebooks are internally generated using mean removed error and Human Visual System (HVS) models. The error model assumed is the Laplacian distribution with mean, lambda-computed from a sample of the input image. A Laplacian distribution with mean, lambda, is generated with uniform random number generator. These random numbers are grouped into vectors. These vectors are further conditioned to make them perceptually meaningful by filtering the DCT coefficients from each vector. The DCT coefficients are filtered by multiplying by a weight matrix that is found to be optimal for human perception. The inverse DCT is performed to produce the conditioned vectors for the codebook. The only image dependent parameter used in the generation of codebook is the mean, lambda, that is included in the coded file to repeat the codebook generation process for decoding.

Manohar, Mareboyana↗

NASA NTRS1996

A New Electron Localization Function and Its Interpretation

A new electron localization function is justified and compared with the laplacian of the electronic charge density. Some advantages of the new function and its novel predictions are discussed. Several slides and some video of visualizations using the new function in comparison to the laplacian will be shown.

Levit, Creon↗

NASA NTRS1997

Bohm's Quantum Potential and the Visualization of Molecular Structure

David Bohm's ontological interpretation of quantum theory can shed light on otherwise counter-intuitive quantum mechanical phenomena including chemical bonding. In the field of quantum chemistry, Richard Bader has shown that the topology of the Laplacian of the electronic charge density characterizes many features of molecular structure and reactivity. Visual and computational examination suggests that the Laplacian of Bader and the quantum potential of Bohm are morphologically equivalent. It appears that Bohmian mechanics and the quantum potential can make chemistry as clear as they makes physics.

Levit, Creon↗

NASA NTRS2004

Curvature-Based Wavefront Sensor for Use on Extended, Arbitrary, Low-Contract Scenes Final Technical Report August 2004

A small amount of work has been done on this project; the strategy to be adopted has been better defined, though no experimental work has been started. 1) Wavefront error signals: The best choice appears use a lenslet array at a pupil image to produce defocused image pairs for each subaperture. Then use the method proposed by Molodij et al. to produce subaperture curvature signals. Basically, this method samples a moderate number of locations in the image where the value of the image Laplacian is high, then taking the curvature signal from the difference of the Laplacians of the extrafocal images at those locations. The tip-tilt error is obtained from the temporal dependence of the first spatial derivatives of an in-focus image, at selected locations where these derivatives are significant. The wavefront tilt can be obtained from the full-aperture image. 2) Extrafocal image generation: The important aspect here is to generate symmetrically defocused images, with dynamically adjustable defocus. The adjustment is needed because larger defocus is required before the feedback loop is closed, and at times when the seeing is worse. It may be that the usual membrane mirror is the best choice, though other options should be explored. 3) Detector: Since the proposed sensor is to work on solar granulation, rather than a point source, an array detector for each subaperture is required. A fast CMOS camera such as that developed by the National Solar Observatory would be a satisfactory choice. 4) Processing: Processing requirements have not been defined in detail, though significantly fewer operations per cycle are required than for a correlation tracker.

LaBonte, Barry J.↗

NASA NTRSDate not supplied

A Proposed Clock Synchronization Method for the Solar System Internet

Networked communications in space are necessary to achieve scalability in terms of the number of communicating nodes but also in terms of the overall system complexity. A key component to such a system is the ability to synchronize clocks, which is the focus of this paper. The so-called Solar System Internet (SSI) will be built upon Delay Tolerant Networking (DTN), which, in analogy to the Internet Protocol (IP), can be considered a suite of protocols necessary for networking in the space domain. Therefore, our goal is to extend this suite to include a DTN clock synchronization capability, analogous to the Network Time Protocol (NTP) used in the Internet. A motivating example of a network in space is NASA’s LunaNet, a vision for a multi-hop multi-path network extending to the moon wherein not all nodes will have direct connections to an authoritative reference clock. In this paper, we propose a general clock synchronization methodology and algorithm that could be used for LunaNet as well as more elaborate time-varying networks. In recent years, DTN has benefited from modeling efforts founded on the mathematical tool of sheaves. Here we continue this work to provide an approach to clock synchronization. Due to the time-varying nature of space networks, absolute consensus is not possible. However, the sheaf Laplacian provides a practical, distributed approach to approximating consensus by allowing data to diffuse through the network. In particular, the sheaf Laplacian is readily computable, lending our approach to implementation. Our approach is well suited to handle the difficulties of space networks. For instance, differences in clock accuracy mean certain nodes are more authoritative than others; we can account for these differences through hierarchies in the network, generalizing the strata in NTP. Furthermore, just as error estimation is an integral part of NTP, we are able to give concrete error bounds for our approach. Indeed, different applications (e.g., communications schedules, pointing, navigation, distributed science) will have different requirements, hence it is necessary to maintain clocks within a given tolerance. We outline some of the necessary steps to turn our approach into a practical network protocol that could be used in DTN, and we conclude the paper with suggestions for future research.

Michael Moy↗