The Givens-Householder method for symmetric matrices.
Givens-Householder method for computing eigenvalues and eigenvectors of real symmetric matrix
SEARCH · Engineering Papers
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.
Givens-Householder method for computing eigenvalues and eigenvectors of real symmetric matrix
Eigenvector scalar product solutions for closed loop time optimal control of linear systems
Equation for linear dynamic systems simplification applicable to all cases irrespective of nature of eigenvalues and eigenvectors
Recent work on eigenvalues and eigenvectors for tensors of order m >= 3 has been motivated by applications in blind source separation, magnetic resonance imaging, molecular conformation, and more. In this paper, we consider methods for computing real symmetric-tensor eigenpairs of the form Ax{sup m-1} = lambda x subject to ||x||=1, which is closely related to optimal rank-1 approximation of a symmetric tensor. Our contribution is a shifted symmetric higher-order power method (SS-HOPM), which we show is guaranteed to converge to a tensor eigenpair. SS-HOPM can be viewed as a generalization of the power iteration method for matrices or of the symmetric higher-order power method. Additionally, using fixed point analysis, we can characterize exactly which eigenpairs can and cannot be found by the method. Numerical examples are presented, including examples from an extension of the method to finding complex eigenpairs.
The Polynomial chaos expansion provides a means of representing any L2 random variable as a sum of polynomials that are orthogonal with respect to a chosen measure. Examples include the Hermite polynomials with Gaussian measure on the real line and the Legendre polynomials with uniform measure on an interval. Polynomial chaos can be used to reformulate an uncertain ODE system, using Galerkin projection, as a new, higher-dimensional, deterministic ODE system which describes the evolution of each mode of the polynomial chaos expansion. It is of interest to explore the eigenstructure of the original and reformulated ODE systems by studying the eigenvalues and eigenvectors of their Jacobians. In this talk, we study the distribution of the eigenvalues of the two Jacobians. We outline in general the location of the eigenvalues of the new system with respect to those of the original system, and examine the effect of expansion order on this distribution.
We propose a sparsity-based space-time adaptive processing (STAP) algorithm to detect a slowly-moving target using an orthogonal frequency division multiplexing (OFDM) radar. We observe that the target and interference spectra are inherently sparse in the spatio-temporal domain, and hence we exploit that sparsity to develop an efficient STAP technique. In addition, the use of an OFDM signal increases the frequency diversity of our system, as different scattering centers of a target resonate at different frequencies, and thus improves the target detectability. First, we formulate a realistic sparse-measurement model for an OFDM radar considering both the clutter and jammer as the interfering sources. Then, we show that the optimal STAP-filter weight-vector is equal to the generalized eigenvector corresponding to the minimum generalized eigenvalue of the interference and target covariance matrices. To estimate the target and interference covariance matrices, we apply a residual sparse-recovery technique that enables us to incorporate the partially known support of the sparse vector. Our numerical results demonstrate that the sparsity-based STAP algorithm, with considerably lesser number of secondary data, produces an equivalent performance as the other existing STAP techniques.
We propose an adaptive waveform design technique for an orthogonal frequency division multiplexing (OFDM) radar signal employing a space-time adaptive processing (STAP) technique. We observe that there are inherent variabilities of the target and interference responses in the frequency domain. Therefore, the use of an OFDM signal can not only increase the frequency diversity of our system, but also improve the target detectability by adaptively modifying the OFDM coefficients in order to exploit the frequency-variabilities of the scenario. First, we formulate a realistic OFDM-STAP measurement model considering the sparse nature of the target and interference spectra in the spatio-temporal domain. Then, we show that the optimal STAP-filter weight-vector is equal to the generalized eigenvector corresponding to the minimum generalized eigenvalue of the interference and target covariance matrices. With numerical examples we demonstrate that the resultant OFDM-STAP filter-weights are adaptable to the frequency-variabilities of the target and interference responses, in addition to the spatio-temporal variabilities. Hence, by better utilizing the frequency variabilities, we propose an adaptive OFDM-waveform design technique, and consequently gain a significant amount of STAP-performance improvement.
We present a method for deriving homogeneous multi-group cross sections to replace a heterogeneous region's multi-group cross sections; providing that the fluxes and the currents on the external boundary, and the region averaged fluxes are preserved. The method is developed using diffusion approximation to the neutron transport equation in a symmetrical slab geometry. Assuming that the boundary fluxes are given, two response matrices (RMs) can be defined. The first derives the boundary current from the boundary flux, the second derives the flux integral over the region from the boundary flux. Assuming that these RMs are known, we present a formula which reconstructs the multi-group cross-section matrix and the diffusion coefficients from the RMs of a homogeneous slab. Applying this formula to the RMs of a slab with multiple homogeneous regions yields a homogenization method; which produce such homogenized multi-group cross sections and homogenized diffusion coefficients, that the fluxes and the currents on the external boundary, and the region averaged fluxes are preserved. The method is based on the determination of the eigenvalues and the eigenvectors of the RMs. We reproduce the four-group cross section matrix and the diffusion constants from the RMs in numerical examples. We give conditions for replacing a heterogeneous region by a homogeneous one so that the boundary current and the region-averaged flux are preserved for a given boundary flux. (authors)
We compare two methods for generating Galerkin quadrature for problems with highly forward-peaked scattering. In Method 1, the standard Sn method is used to generate the moment-to-discrete matrix and the discrete-to-moment is generated by inverting the moment-to-discrete matrix. In Method 2, which we introduce here, the standard Sn method is used to generate the discrete-to-moment matrix and the moment-to-discrete matrix is generated by inverting the discrete-to-moment matrix. Method 1 has the advantage that it preserves both N eigenvalues and N eigenvectors (in a pointwise sense) of the scattering operator with an N-point quadrature. Method 2 has the advantage that it generates consistent angular moment equations from the corresponding S{sub N} equations while preserving N eigenvalues of the scattering operator with an N-point quadrature. Our computational results indicate that these two methods are quite comparable for the test problem considered. (authors)
The equation of photon transport in directionally discretized 2N streams has been the subject of various numerical algorithms over the past 65 years since Chandrasekhar first explored the concept. The importance of this equation cannot be overemphasized, as it characterizes neutral particles (in this case photons) undergoing collisions as characterized by the scattering phase function in a 1D slab medium. More precisely, particles enter a homogeneous slab medium with the particle intensity distribution to be numerically determined. We find applications in light scattering for graphical rendering as well as deep penetration photon transport in a scattering medium as considered here. Noting the algebraic nature of the solution, numerous numerical attempts at an efficient algorithm have appeared in the literature-- many involving numerical linear algebra. Most notable are the Discrete Ordinates Method [DOM] of Stamnes and the Analytical Discrete Ordinates (ADO) method of Siewert as well as the Laplace Transform (LTSN) method of Vilhena. The methods are all centered on the determination of eigenvalues (or zeros of a polynomial in the case of the LTSN method) of a linear system enabling the solution to be represented as a sum of exponential eigenvectors. Because of the unstable nature of the solution, unless one takes care, such a representation leads to numerical catastrophe. Here, we derive an alternative form of solution to overcome this difficulty for application to deep penetration.
We analyze numerical behavior of the eigenvectors corresponding to the lowest eigenvalues of the generalized graph Laplacians arising in the Normalized Cuts formulations of the image segmentation problem on coarse polygonal grids.
Many detection algorithms in hyperspectral image analysis, from well-characterized gaseous and solid targets to deliberately uncharacterized anomalies and anomlous changes, depend on accurately estimating the covariance matrix of the background. In practice, the background covariance is estimated from samples in the image, and imprecision in this estimate can lead to a loss of detection power. In this paper, we describe the sparse matrix transform (SMT) and investigate its utility for estimating the covariance matrix from a limited number of samples. The SMT is formed by a product of pairwise coordinate (Givens) rotations, which can be efficiently estimated using greedy optimization. Experiments on hyperspectral data show that the estimate accurately reproduces even small eigenvalues and eigenvectors. In particular, we find that using the SMT to estimate the covariance matrix used in the adaptive matched filter leads to consistently higher signal-to-noise ratios.
Machine learning (ML) is relied on for materials spectroscopy. It is challenging to make ML models fail because statistical correlations can mimic the physics without causality. Here, using a benchmark band-excitation piezoresponse force microscopy polarization spectroscopy (BEPS) dataset the pitfalls of the so-called “better”, “faster”, and “less-biased” ML of electromechanical switching are demonstrated and overcome. Using a toy and real experimental dataset, it is demonstrated how linear nontemporal ML methods result in physically reasonable embedding (eigenvalues) while producing nonsensical eigenvectors and generated spectra, promoting misleading interpretations. A new method of unsupervised multimodal hyperspectral analysis of BEPS is demonstrated using long-short-term memory (LSTM) β-variational autoencoders (β-VAEs) . By including LSTM neurons, the ordinal nature of ferroelectric switching is considered. Further, to improve the interpretability of the latent space, a variational Kullback–Leibler-divergency regularization is imposed . Finally, regularization scheduling of β as a disentanglement metric is leveraged to reduce user bias. Combining these experiment-inspired modifications enables the automated detection of ferroelectric switching mechanisms, including a complex two-step, three-state one. Ultimately, this work provides a robust ML method for the rapid discovery of electromechanical switching mechanisms in ferroelectrics and is applicable to other multimodal hyperspectral materials spectroscopies.
Graph Laplacian is a popular tool for analyzing graphs, particularly in graph partitioning and clustering. Given a notion of similarity (via an adjacency matrix), graph clustering refers to identifying different groups such that vertices in the same group are more similar compared to vertices across different groups. Data clustering can be reformulated in terms of a graph clustering problem when the given set of data is represented as a graph, also known as similarity graph. In this context, eigenvectors of the graph Laplacian are often used to obtain a new geometric representation of the original data set that generally enhances cluster properties and improves cluster detection. Here, we apply a bootstrap algebraic multigrid (AMG) method that constructs a set of vectors associated with the graph Laplacian. These vectors, referred to as algebraically smooth ones, span a low-dimensional Euclidean space, which we use to represent the data, enabling cluster detection both in synthetic and in realistic well-clustered graphs. We show that, in the case of a good quality bootstrap AMG, the computed smooth vectors employed in the construction of the final AMG operator, which by construction is spectrally equivalent to the originally given graph Laplacian, accurately approximate the space in the lower portion of the spectrum of the preconditioned operator. Thus, our approach can be viewed as a spectral clustering technique associated with the generalized spectral problem (Laplace operator versus the final AMG operator), and hence, it can be seen as an extension of the classical spectral clustering that employs a standard eigenvalue problem.
The Shift-and-invert parallel spectral transformations (SIPs), a computational approach to solve sparse eigenvalue problems, is developed for massively parallel architectures with exceptional parallel scalability and robustness. The capabilities of SIPs are demonstrated by diagonalization of density-functional based tight-binding (DFTB) Hamiltonian and overlap matrices for single-wall metallic carbon nanotubes, diamond nanowires, and bulk diamond crystals. The largest (smallest) example studied is a 128,000 (2000) atom nanotube for which ~330,000 (~5600) eigenvalues and eigenfunctions are obtained in ~190 (~5) seconds when parallelized over 266,144 (16,384) Blue Gene/Q cores. Weak scaling and strong scaling of SIPs are analyzed and the performance of SIPs is compared with other novel methods. Different matrix ordering methods are investigated to reduce the cost of the factorization step, which dominates the time-to-solution at the strong scaling limit. As a result, a parallel implementation of assembling the density matrix from the distributed eigenvectors is demonstrated.
The vibrational and rotational mode-specific relaxations of CH 3 NO 2 with 50 kcal/mol of initial internal energy in an argon bath is computed at 300 K at pressures of 10-400 atm. This work uses archived information from our previously published [J. Chem. Phys. 142, 014303 (2015)] molecular dynamics simulations and employs our previous published [J. Chem. Phys. 151, 034303 (2019)] method for projecting time-dependent Cartesian velocities onto normal mode eigenvectors. The computed relaxations cover three types of energies: vibrational, rotational, and Coriolis. In general, rotational and Coriolis relaxations in all modes are initially fast followed by an orders of magnitude slower relaxation. For all modes, that slower relaxation rate is approximately comparable to the vibrational relaxation rate. For all three types of energies, there are small-scale mode-to-mode variations. Of particular prominence is the exceptionally fast relaxation shared in common by the external rotation about the C-N axis, the internal hindered rotation of the CH 3 group relative to the NO 2 group, and the symmetric stretch of the CH 3 group.
This work discusses techniques for computing a few selected eigenvalue–eigenvector pairs of large and sparse symmetric matrices. A recently developed class of techniques to solve this type of problems is based on integrating the matrix resolvent operator along a complex contour that encloses the interval containing the eigenvalues of interest. This paper considers such contour integration techniques from a domain decomposition viewpoint and proposes two schemes. The first scheme can be seen as an extension of domain decomposition linear system solvers in the framework of contour integration methods for eigenvalue problems, such as FEAST. The second scheme focuses on integrating the resolvent operator primarily along the interface region defined by adjacent subdomains. A parallel implementation of the proposed schemes is described, and results on distributed computing environments are reported. These results show that domain decomposition approaches can lead to reduced run times and improved scalability.
Abstract The effective inclusion of a priori knowledge when embedding known data in physics‐based models of dynamical systems can ensure that the reconstructed model respects physical principles, while simultaneously improving the accuracy of the solution in the previously unseen regions of state space. This paper presents a physics‐constrained data‐driven discrepancy modeling method that variationally embeds known data in the modeling framework. The hierarchical structure of the method yields fine scale variational equations that facilitate the derivation of residuals which are comprised of the first‐principles theory and sensor‐based data from the dynamical system. The embedding of the sensor data via residual terms leads to discrepancy‐informed closure models that yield a method which is driven not only by boundary and initial conditions, but also by measurements that are taken at only a few observation points in the target system. Specifically, the data‐embedding term serves as residual‐based least‐squares loss function, thus retaining variational consistency. Another important relation arises from the interpretation of the stabilization tensor as a kernel function, thereby incorporating a priori knowledge of the problem and adding computational intelligence to the modeling framework. Numerical test cases show that when known data is taken into account, the data driven variational (DDV) method can correctly predict the system response in the presence of several types of discrepancies. Specifically, the damped solution and correct energy time histories are recovered by including known data in the undamped situation. Morlet wavelet analyses reveal that the surrogate problem with embedded data recovers the fundamental frequency band of the target system. The enhanced stability and accuracy of the DDV method is manifested via reconstructed displacement and velocity fields that yield time histories of strain and kinetic energies which match the target systems. The proposed DDV method also serves as a procedure for restoring eigenvalues and eigenvectors of a deficient dynamical system when known data is taken into account, as shown in the numerical test cases presented here.