Augmented canonical forms and factorization of graphs

The main aim of this paper is to generalize the previously developed canonical forms by different types of alterations and/or augmentations. These forms provide suitable tools for the decomposition of the matrices of special patterns and lead to efficient aproaches for calculating their eigenvalues. Methods were developed for factorization of symmetric graphs into smaller subgraphs using decompostion and healings (Commun. Numer. Meth. Engng 2003; 19 :125–136, 2004; 20 :133–146, 2004; 20 :889–910; Comput. Struct. 2004; 18 :2229–2240). Further factorization was possible only when further symmetries were available. The main drawback was associated with non‐decomposiblity of some of the factors in early stages of decomposition, and in particular healing which often destroyed the symmetry. In this paper, the mathematical concepts related to certain symmetric and unsymmetric graphs are developed, making refined factorization of the graphs feasible. Examples are included to show the simplicity of the operations being involved. Copyright © 2005 John Wiley & Sons, Ltd.     

Block diagonalization of Laplacian matrices of symmetric graphs via group theory

In this article, group theory is employed for block diagonalization of Laplacian matrices of symmetric graphs. The inter‐relation between group diagonalization methods and algebraic‐graph methods developed in recent years are established. Efficient methods are presented for calculating the eigenvalues and eigenvectors of matrices having canonical patterns. This is achieved by using concepts from group theory, linear algebra, and graph theory. These methods, which can be viewed as extensions to the previously developed approaches, are illustrated by applying to the eigensolution of the Laplacian matrices of symmetric graphs. The methods of this paper can be applied to combinatorial optimization problems such as nodal and element ordering and graph partitioning by calculating the second eigenvalue for the Laplacian matrices of the models and the formation of their Fiedler vectors. Considering the graphs as the topological models of skeletal structures, the present methods become applicable to the calculation of the buckling loads and the natural frequencies and natural modes of skeletal structures. Copyright © 2006 John Wiley & Sons, Ltd.     

Simultaneous tridiagonalization of two symmetric matrices

We show how to simultaneously reduce a pair of symmetric matrices to tridiagonal form by congruence transformations. No assumptions are made on the non‐singularity or definiteness of the two matrices. The reduction follows a strategy similar to the one used for the tridiagonalization of a single symmetric matrix via Householder reflectors. Two algorithms are proposed, one using non‐orthogonal rank‐one modifications of the identity matrix and the other, more costly but more stable, using a combination of Householder reflectors and non‐orthogonal rank‐one modifications of the identity matrix with minimal condition numbers. Each of these tridiagonalization processes requires O(n³) arithmetic operations and respects the symmetry of the problem. We illustrate and compare the two algorithms with some numerical experiments. Copyright © 2003 John Wiley & Sons, Ltd.     

Implicit boundary method for analysis using uniform B‐spline basis and structured grid

Several analysis techniques such as extended finite element method (X‐FEM) have been developed recently, which use structured grid for the analysis. Implicit boundary method uses implicit equations of the boundary to apply boundary conditions in X‐FEM framework using structured grids. Solution structures for test and trial functions are constructed using implicit equations such that the boundary conditions are satisfied even if there are no nodes on the boundary. In this paper, this method is applied for analysis using uniform B‐spline basis defined over a structured grid. Solution structures that are C¹ or C² continuous throughout the analysis domain can be constructed using B‐spline basis functions. As a structured grid does not conform to the geometry of the analysis domain, the boundaries of the analysis domain are defined independently using equations of the boundary curves/surfaces. Compared with conforming mesh, it is easier to generate structured grids that overlap the geometry and the elements in the grid are regular shaped and undistorted. Numerical examples are presented to demonstrate the performance of these B‐spline elements. The results are compared with analytical solutions as well as with traditional finite element solutions. Convergence studies for several examples show that B‐spline elements provide accurate solutions with fewer elements and nodes compared with traditional FEM. They also provide continuous stress and strain in the analysis domain, thus eliminating the need for smoothing stress/strain results. Copyright © 2008 John Wiley & Sons, Ltd.     

Eigensolution of augmented graph products using shifted inverse iteration method

Two important matrices associated with graphs are adjacency and Laplacian matrices. In this paper efficient methods are presented for eigensolution of graph products augmented by other graphs. For augmentations that do not destroy the symmetry of the graph products, a method is proposed for decomposition of matrices resulting in considerable simplification of their eigensolution. For graphs composed of two non‐overlapping graph products joined through a small number of link members, a method based on shifted inverse iteration is proposed which utilizes all eigenvalues and eigenvectors of each individual graph products. Owing to the availability of fast methods for eigensolution of graph products, this method simplifies the eigensolution of a variety of graph models and proves to be very efficient in determining the few smallest eigenpairs of these models with high levels of accuracy. Copyright © 2010 John Wiley & Sons, Ltd.     

The generalized global basis (GGB) method

In this work, we present the generalized global basis (GGB) method aimed at enhancing performance of multilevel solvers for difficult systems such as those arising from indefinite and non‐symmetric matrices. The GGB method is based on the global basis (GB) method (Int J Numer Methods Eng 2000; 49 :439–460, 461–478), which constructs an auxiliary coarse model from the largest eigenvalues of the iteration matrix. The GGB method projects these modes which would cause slow convergence to a coarse problem which is then used to eliminate these modes. Numerical examples show that best performance is obtained when GGB is accelerated by GMRES and used for problems with multiple right‐hand sides. In addition, it is demonstrated that GGB method can enhance restarted GMRES strategies by retention of subspace information. Copyright © 2004 John Wiley & Sons, Ltd.     

Factorization for efficient solution of eigenproblems of adjacency and Laplacian matrices for graph products

Many structural models can be generated as the graph products of two or three subgraphs known as their generators. The main types of graph products consist of Cartesian, strong Cartesian, direct, and lexicographic products. In this paper, a general method is presented for the factorization of these graph products, such that the eigenvalues of the entire graph are obtained as the union of the eigenvalues of the weighted subgraphs defined here. The adjacency and Laplacian matrices for each graph product are studied separately. For graphs with missing elements (cut‐outs), the eigenvalues are calculated with the additional use of the Rayleigh quotient approach. The main idea stems from the rules recently developed by the authors for block diagonalization of matrices. These products have many applications in computational mechanics, such as ordering, graph partitioning, dynamic analysis, and stability analysis of structures. Some of these applications are addressed in this paper. Copyright © 2007 John Wiley & Sons, Ltd.     

Study of fullerenes via their symmetry groups

In this paper, we compute the automorphism group of some infinite classes of fullerene graphs and then we compute their symmetric Szeged index which is a new topological index based on the automorphism group.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

vibro‐Lanczos,a symmetric Lanczos solver for vibro‐acoustic simulations

An efficient symmetric Lanczos method for the solution of vibro‐acoustic eigenvalue problems is presented in this paper. Although finite element discretization results in real but nonsymmetric system matrices, we show that an efficient iteration scheme on a symmetric representation can be built up by using a transformation matrix. In order to decrease the numerical costs of the orthogonalizations performed, we propose to use a partial orthogonalization scheme for the symmetric case. The proposed method is tested on two large problems in order to demonstrate its efficiency and accuracy. Copyright © 2016 John Wiley & Sons, Ltd.     

Backward Error Analysis for an Eigenproblem Involving Two Classes of Matrices

We consider backward errors for an eigenproblem of a class of symmetric generalised centrosymmetric matrices and skew-symmetric generalised skew-centrosymmetric matrices, which are extensions of symmetric centrosymmetric and skew-symmetric skew-centrosymmetric matrices. Explicit formulae are presented for the computable backward errors for approximate eigenpairs of these two kinds of structured matrices. Numerical examples illustrate our results.     

Dimensional reduction of nonlinear finite element dynamic models with finite rotations and energy‐based mesh sampling and weighting for computational efficiency

A rigorous computational framework for the dimensional reduction of discrete, high‐fidelity, nonlinear, finite element structural dynamics models is presented. It is based on the pre‐computation of solution snapshots, their compression into a reduced‐order basis, and the Galerkin projection of the given discrete high‐dimensional model onto this basis. To this effect, this framework distinguishes between vector‐valued displacements and manifold‐valued finite rotations. To minimize computational complexity, it also differentiates between the cases of constant and configuration‐dependent mass matrices. Like most projection‐based nonlinear model reduction methods, however, its computational efficiency hinges not only on the ability of the constructed reduced‐order basis to capture the dominant features of the solution of interest but also on the ability of this framework to compute fast and accurate approximations of the projection onto a subspace of tangent matrices and/or force vectors. The computation of the latter approximations is often referred to in the literature as hyper reduction. Hence, this paper also presents the energy‐conserving sampling and weighting (ECSW) hyper reduction method for discrete (or semi‐discrete), nonlinear, finite element structural dynamics models. Based on mesh sampling and the principle of virtual work, ECSW is natural for finite element computations and preserves an important energetic aspect of the high‐dimensional finite element model to be reduced. Equipped with this hyper reduction procedure, the aforementioned Galerkin projection framework is first demonstrated for several academic but challenging problems. Then, its potential for the effective solution of real problems is highlighted with the realistic simulation of the transient response of a vehicle to an underbody blast event. For this problem, the proposed nonlinear model reduction framework reduces the CPU time required by a typical high‐dimensional model by up to four orders of magnitude while maintaining a good level of accuracy. Copyright © 2014 John Wiley & Sons, Ltd.     

A fully symmetric multi‐zone Galerkin boundary element method

This paper examines the efficient integration of a Symmetric Galerkin Boundary Element Analysis (SGBEA) method with multi‐zone resulting in a fully symmetric Galerkin multi‐zone formulation. In a previous approach, a Galerkin multi‐zone method was developed where the interfacial nodes are assigned degrees of freedom globally so that the displacement and traction continuity across the zonal interfaces are addressed directly. However, the method was only block symmetric. In the present paper, two new approaches are derived. In the first approach, the degrees of freedom for a particular zone are assigned locally, independent of the other zones. The usual linear set of equations, from the symmetric Galerkin approach, are augmented with an additional set of equations generated by the Galerkin form of hypersingular boundary integrals along the interfaces. Zonal continuity is imposed externally through Lagrange's constraints. This approach is also only block symmetric. The second approach derived from the first, uses the continuity constraints at the zonal assembly level to achieve full symmetry. These methods are compared to collocation multi‐zone and an earlier formulation, on two elasticity problems from the literature. It was found that the second method is much faster than the collocation method for medium to large scale problems, primarily due to its complete symmetry. It is also observed that these methods spend marginally more time on integration than the previous Galerkin multi‐zone method but are better suited to parallel processing. Copyright © 1999 John Wiley & Sons, Ltd.     

Block diagonalization of adjacency and Laplacian matrices for graph product; applications in structural mechanics

Eigenvalues and eigenvectors of graphs have many applications in structural mechanics and combinatorial optimization. For a regular space structure, the visualization of its graph model as the product of two simple graphs results in a substantial simplification in the solution of the corresponding eigenproblems. In this paper, the adjacency and Laplacian matrices of four graph products, namely, Cartesian, strong Cartesian, direct and lexicographic products are diagonalized and efficient methods are obtained for calculating their eigenvalues and eigenvectors. An exceptionally efficient method is developed for the eigensolution of the Laplacian matrices of strong Cartesian and direct products. Special attention is paid to the lexicographic product, which is not studied in the past as extensively as the other three graph products. Examples are provided to illustrate some applications of the methods in structural mechanics. Copyright © 2006 John Wiley & Sons, Ltd.     

An extended QR‐solver for large profiled matrices

A new method for the solution of the standard eigenvalue problem with large symmetric profile matrices is presented. The method is based on the well‐known QR‐method for dense matrices. A new, flexible and reliable extension of the method is developed that is highly suited for the independent computation of any set of eigenvalues. In order to analyze the weak convergence of the method in the presence of clustered eigenvalues, the QR‐method is studied. Two effective, stable and numerically cheap extensions are introduced to overcome the troublesome stagnation of the convergence. A repeated preconditioning process in combination with Jacobi rotations in the parts of the matrix with the strongest convergence is developed to significantly improve both local and global convergence. The extensions preserve the profile structure of the matrix. The efficiency of the new method is demonstrated with several examples. Copyright © 2009 John Wiley & Sons, Ltd.     

Structured pseudospectra in structural engineering

This paper presents a new method for computing the pseudospectra of a matrix that respects a prescribed sparsity structure. The pseudospectrum is defined as the set of points in the complex plane to which an eigenvalue of the matrix can be shifted by a perturbation of a certain size. A canonical form for sparsity preserving perturbations is given and a computable formula for the corresponding structured pseudospectra is derived. This formula relates the computation of structured pseudospectra to the computation of the structured singular value (ssv) of an associated matrix. Although the computation of the ssv in general is an NP‐hard problem, algorithms for its approximation are available and demonstrate good performance when applied to the computation of structured pseudospectra of medium‐sized or highly sparse matrices. The method is applied to a wing vibration problem, where it is compared with the matrix polynomial approach, and to the stability analysis of truss structures. New measures for the vulnerability of a truss structure are proposed, which are related to the ‘distance to singularity’ of the associated stiffness matrix. Copyright © 2005 John Wiley & Sons, Ltd.     

Topological aspects of meshless methods and nodal ordering for meshless discretizations

The meshless element‐free Galerkin method (EFGM) is considered and compared to the finite‐element method (FEM). In particular, topological aspects of meshless methods as the nodal connectivity and invertibility of matrices are studied and compared to those of the FE method. We define four associated graphs for meshless discretizations of EFGM and investigate their connectivity. The ways that the associated graphs for coupled FE‐EFG models might be defined are recommended. The associated graphs are used for nodal ordering of meshless models in order to reduce the bandwidth, profile, maximum frontwidth, and root‐mean‐square wavefront of the corresponding matrices. Finally, the associated graphs are numerically compared. Copyright © 2001 John Wiley & Sons, Ltd.     

Accelerated mesh sampling for the hyper reduction of nonlinear computational models

In nonlinear model order reduction, hyper reduction designates the process of approximating a projection‐based reduced‐order operator on a reduced mesh, using a numerical algorithm whose computational complexity scales with the small size of the projection‐based reduced‐order model. Usually, the reduced mesh is constructed by sampling the large‐scale mesh associated with the high‐dimensional model underlying the projection‐based reduced‐order model. The sampling process itself is governed by the minimization of the size of the reduced mesh for which the hyper reduction method of interest delivers the desired accuracy for a chosen set of training reduced‐order quantities. Because such a construction procedure is combinatorially hard, its key objective function is conveniently substituted with a convex approximation. Nevertheless, for large‐scale meshes, the resulting mesh sampling procedure remains computationally intensive. In this paper, three different convex approximations that promote sparsity in the solution are considered for constructing reduced meshes that are suitable for hyper reduction and paired with appropriate active set algorithms for solving the resulting minimization problems. These algorithms are equipped with carefully designed parallel computational kernels in order to accelerate the overall process of mesh sampling for hyper reduction, and therefore achieve practicality for realistic, large‐scale, nonlinear structural dynamics problems. Conclusions are also offered as to what algorithm is most suitable for constructing a reduced mesh for the purpose of hyper reduction. Copyright © 2016 John Wiley & Sons, Ltd.     

Structured extended finite element methods for solids defined by implicit surfaces

A paradigm is developed for generating structured finite element models from solid models by means of implicit surface definitions. The implicit surfaces are defined by radial basis functions. Internal features, such as material interfaces, sliding interfaces and cracks are treated by enrichment techniques developed in the extended finite element method. Methods for integrating the weak form for such models are proposed. These methods simplify the generation of finite element models. Results presented for several examples show that the accuracy of this method is comparable to standard unstructured finite element methods. Copyright © 2002 John Wiley & Sons, Ltd.     

线性流形上复对称矩阵的最小二乘问题

本文主要讨论了线性流形上复对称矩阵的最小二乘问题。在推导出所给线性流形中任意矩阵的显式表达的基础上,利用奇异值分解和Frobenius范数的酉不变性得到了该最小二乘问题通解的一般表达式。此外,文章还考虑了任一给定矩阵对此最小二乘问题解集合的最佳逼近问题,证明了该最佳逼近问题存在唯一解,并利用酉矩阵的性质得到了最佳逼近解的表达式。