Showing 1–36 of 36 results for author: Cui, C

Acceleration of Tensor-Product Operations with Tensor Cores

Authors: Cu Cui

Abstract: In this paper, we explore the acceleration of tensor product operations in finite element methods, leveraging the computational power of the NVIDIA A100 GPU Tensor Cores. We provide an accessible overview of the necessary mathematical background and discuss our implementation strategies. Our study focuses on two common programming approaches for NVIDIA Tensor Cores: the C++ Warp Matrix Functions i… ▽ More In this paper, we explore the acceleration of tensor product operations in finite element methods, leveraging the computational power of the NVIDIA A100 GPU Tensor Cores. We provide an accessible overview of the necessary mathematical background and discuss our implementation strategies. Our study focuses on two common programming approaches for NVIDIA Tensor Cores: the C++ Warp Matrix Functions in nvcuda::wmma and the inline Parallel Thread Execution (PTX) instructions mma.sync.aligned. A significant focus is placed on the adoption of the versatile inline PTX instructions combined with a conflict-free shared memory access pattern, a key to unlocking superior performance. When benchmarked against traditional CUDA Cores, our approach yields a remarkable 2.3-fold increase in double precision performance, achieving 8 TFLOPS/s-45% of the theoretical maximum. Furthermore, in half-precision computations, numerical experiments demonstrate a fourfold enhancement in solving the Poisson equation using the flexible GMRES (FGMRES) method, preconditioned by a multigrid method in 3D. This is achieved while maintaining the same discretization error as observed in double precision computations. These results highlight the considerable benefits of using Tensor Cores for finite element operators with tensor products, achieving an optimal balance between computational speed and precision. △ Less

Submitted 12 July, 2024; originally announced July 2024.

ACM Class: G.1.8; G.4

Extended alternating structure-adapted proximal gradient algorithm for nonconvex nonsmooth problems

Authors: Ying Gao, Chunfeng Cui, Wenxing Zhang, Deren Han

Abstract: Alternating structure-adapted proximal (ASAP) gradient algorithm (M. Nikolova and P. Tan, SIAM J Optim, 29:2053-2078, 2019) has drawn much attention due to its efficiency in solving nonconvex nonsmooth optimization problems. However, the multiblock nonseparable structure confines the performance of ASAP to far-reaching practical problems, e.g., coupled tensor decomposition. In this paper, we propo… ▽ More Alternating structure-adapted proximal (ASAP) gradient algorithm (M. Nikolova and P. Tan, SIAM J Optim, 29:2053-2078, 2019) has drawn much attention due to its efficiency in solving nonconvex nonsmooth optimization problems. However, the multiblock nonseparable structure confines the performance of ASAP to far-reaching practical problems, e.g., coupled tensor decomposition. In this paper, we propose an extended ASAP (eASAP) algorithm for nonconvex nonsmooth optimization whose objective is the sum of two nonseperable functions and a coupling one. By exploiting the blockwise restricted prox-regularity, eASAP is capable of minimizing the objective whose coupling function is multiblock nonseparable. Moreover, we analyze the global convergence of eASAP by virtue of the Aubin property on partial subdifferential mapping and the Kurdyka-Łojasiewicz property on the objective. Furthermore, the sublinear convergence rate of eASAP is built upon the proximal point algorithmic framework under some mild conditions. Numerical simulations on multimodal data fusion demonstrate the compelling performance of the proposed method. △ Less

Submitted 24 June, 2024; originally announced June 2024.

An implementation of tensor product patch smoothers on GPU

Authors: Cu Cui, Paul Grosse-Bley, Guido Kanschat, Robert Strzodka

Abstract: We present a GPU implementation of vertex-patch smoothers for higher order finite element methods in two and three dimensions. Analysis shows that they are not memory bound with respect to GPU DRAM, but with respect to on-chip scratchpad memory. Multigrid operations are optimized through localization and reorganized local operations in on-chip memory, achieving minimal global data transfer and a c… ▽ More We present a GPU implementation of vertex-patch smoothers for higher order finite element methods in two and three dimensions. Analysis shows that they are not memory bound with respect to GPU DRAM, but with respect to on-chip scratchpad memory. Multigrid operations are optimized through localization and reorganized local operations in on-chip memory, achieving minimal global data transfer and a conflict free memory access pattern. Performance tests demonstrate that the optimized kernel is at least 2 times faster than the straightforward implementation for the Poisson problem, across various polynomial degrees in 2D and 3D, achieving up to 36% of the peak performance in both single and double precision on Nvidia A100 GPU. △ Less

Submitted 30 May, 2024; v1 submitted 29 May, 2024; originally announced May 2024.

MSC Class: 65N55; 65Y20

Multilevel Interior Penalty Methods on GPUs

Authors: Cu Cui, Guido Kanschat

Abstract: We present a matrix-free multigrid method for high-order discontinuous Galerkin (DG) finite element methods with GPU acceleration. A performance analysis is conducted, comparing various data and compute layouts. Smoother implementations are optimized through localization and fast diagonalization techniques. Leveraging conflict-free access patterns in shared memory, arithmetic throughput of up to 3… ▽ More We present a matrix-free multigrid method for high-order discontinuous Galerkin (DG) finite element methods with GPU acceleration. A performance analysis is conducted, comparing various data and compute layouts. Smoother implementations are optimized through localization and fast diagonalization techniques. Leveraging conflict-free access patterns in shared memory, arithmetic throughput of up to 39% of the peak performance on Nvidia A100 GPUs are achieved. Experimental results affirm the effectiveness of mixed-precision approaches and MPI parallelization in accelerating algorithms. Furthermore, an assessment of solver efficiency and robustness is provided across both two and three dimensions, with applications to Poisson problems. △ Less

Submitted 30 May, 2024; v1 submitted 29 May, 2024; originally announced May 2024.

MSC Class: 65N55; 65Y20

Moore Determinant of Dual Quaternion Hermitian Matrices

Authors: Chunfeng Cui, Liqun Qi, Guangjing Song, Qingwen Wang

Abstract: In this paper, we extend the Chen and Moore determinants of quaternion Hermitian} matrices to dual quaternion Hermitian matrices. We show the Chen determinant of dual quaternion Hermitian {matrices is invariant under addition, switching, multiplication, and unitary operations at the both hand sides. We then show the Chen and Moore determinants of dual quaternion Hermitian matrices are equal to eac… ▽ More In this paper, we extend the Chen and Moore determinants of quaternion Hermitian} matrices to dual quaternion Hermitian matrices. We show the Chen determinant of dual quaternion Hermitian {matrices is invariant under addition, switching, multiplication, and unitary operations at the both hand sides. We then show the Chen and Moore determinants of dual quaternion Hermitian matrices are equal to each other, and they are also equal to the products of eigenvalues. The characteristic polynomial of a dual quaternion Hermitian matrix is also studied. △ Less

Submitted 18 May, 2024; v1 submitted 6 May, 2024; originally announced May 2024.

Non-convex Pose Graph Optimization in SLAM via Proximal Linearized Riemannian ADMM

Authors: Xin Chen, Chunfeng Cui, Deren Han, Liqun Qi

Abstract: Pose graph optimization (PGO) is a well-known technique for solving the pose-based simultaneous localization and mapping (SLAM) problem. In this paper, we represent the rotation and translation by a unit quaternion and a three-dimensional vector, and propose a new PGO model based on the von Mises-Fisher distribution. The constraints derived from the unit quaternions are spherical manifolds, and th… ▽ More Pose graph optimization (PGO) is a well-known technique for solving the pose-based simultaneous localization and mapping (SLAM) problem. In this paper, we represent the rotation and translation by a unit quaternion and a three-dimensional vector, and propose a new PGO model based on the von Mises-Fisher distribution. The constraints derived from the unit quaternions are spherical manifolds, and the projection onto the constraints can be calculated by normalization. Then a proximal linearized Riemannian alternating direction method of multipliers (PieADMM) is developed to solve the proposed model, which not only has low memory requirements, but also can update the poses in parallel. Furthermore, we establish the iteration complexity of $O(1/ε^{2})$ of PieADMM for finding an $ε$-stationary solution of our model. The efficiency of our proposed algorithm is demonstrated by numerical experiments on two synthetic and four 3D SLAM benchmark datasets. △ Less

Submitted 29 April, 2024; originally announced April 2024.

A Neural Multigrid Solver for Helmholtz Equations with High Wavenumber and Heterogeneous Media

Authors: Chen Cui, Kai Jiang, Shi Shu

Abstract: Solving high-wavenumber and heterogeneous Helmholtz equations presents a long-standing challenge in scientific computing. In this paper, we introduce a deep learning-enhanced multigrid solver to address this issue. By conducting error analysis on standard multigrid applied to a discrete Helmholtz equation, we devise a strategy to handle errors with different frequencies separately. For error com… ▽ More Solving high-wavenumber and heterogeneous Helmholtz equations presents a long-standing challenge in scientific computing. In this paper, we introduce a deep learning-enhanced multigrid solver to address this issue. By conducting error analysis on standard multigrid applied to a discrete Helmholtz equation, we devise a strategy to handle errors with different frequencies separately. For error components with frequencies distant from the wavenumber, we perform simple smoothing based on local operations at different levels to eliminate them. On the other hand, to address error components with frequencies near the wavenumber, we utilize another multigrid V-cycle to solve an advection-diffusion-reaction (ADR) equation at a coarse scale. The resulting solver, named Wave-ADR-NS, involves parameters learned through unsupervised training. Numerical results demonstrate that Wave-ADR-NS effectively resolves heterogeneous 2D Helmholtz equation with wavenumber up to 2000. Comparative experiments against classical multigrid preconditioners and existing deep learning-based multigrid preconditioners reveals the superior performance of Wave-ADR-NS. △ Less

Submitted 3 April, 2024; originally announced April 2024.

MSC Class: 65N22; 65N55; 68T07

Eigenvalues of Dual Hermitian Matrices with Application in Formation Control

Authors: Liqun Qi, Chunfeng Cui

Abstract: We propose a supplement matrix method for computing eigenvalues of a dual Hermitian matrix, and discuss its application in multi-agent formation control. Suppose we have a ring, which can be the real field, the complex field, or the quaternion ring. We study dual number symmetric matrices, dual complex Hermitian matrices and dual quaternion Hermitian matrices in a unified frame of dual Hermitian m… ▽ More We propose a supplement matrix method for computing eigenvalues of a dual Hermitian matrix, and discuss its application in multi-agent formation control. Suppose we have a ring, which can be the real field, the complex field, or the quaternion ring. We study dual number symmetric matrices, dual complex Hermitian matrices and dual quaternion Hermitian matrices in a unified frame of dual Hermitian matrices. An $n \times n$ dual Hermitian matrix has $n$ dual number eigenvalues. We define determinant, characteristic polynomial and supplement matrices for a dual Hermitian matrix. Supplement matrices are Hermitian matrices in the original ring. The standard parts of the eigenvalues of that dual Hermitian matrix are the eigenvalues of the standard part Hermitian matrix in the original ring, while the dual parts of the eigenvalues of that dual Hermitian matrix are the eigenvalues of those supplement matrices. Hence, by applying any practical method for computing eigenvalues of Hermitian matrices in the original ring, we have a practical method for computing eigenvalues of a dual Hermitian matrix. We call this method the supplement matrix method. In multi-agent formation control, a desired relative configuration scheme may be given. People need to know if this scheme is reasonable such that a feasible solution of configurations of these multi-agents exists. By exploring the eigenvalue problem of dual Hermitian matrices, and its link with the unit gain graph theory, we open a cross-disciplinary approach to solve the relative configuration problem. Numerical experiments are reported. △ Less

Submitted 1 April, 2024; v1 submitted 15 March, 2024; originally announced March 2024.

Comments: arXiv admin note: text overlap with arXiv:2402.12988

Inertial Accelerated Stochastic Mirror Descent for Large-Scale Generalized Tensor CP Decomposition

Authors: Zehui Liu, Qingsong Wang, Chunfeng Cui, Yong Xia

Abstract: The majority of classic tensor CP decomposition models are designed for squared loss, employing Euclidean distance as a local proximal term. However, the Euclidean distance is unsuitable for the generalized loss function applicable to various types of real-world data, such as integer and binary data. Consequently, algorithms developed under the squared loss are not easily adaptable to handle these… ▽ More The majority of classic tensor CP decomposition models are designed for squared loss, employing Euclidean distance as a local proximal term. However, the Euclidean distance is unsuitable for the generalized loss function applicable to various types of real-world data, such as integer and binary data. Consequently, algorithms developed under the squared loss are not easily adaptable to handle these generalized losses, partially due to the lack of the gradient Lipschitz continuity. This paper considers the generalized tensor CP decomposition. We use the Bregman distance as the proximal term and propose an inertial accelerated block randomized stochastic mirror descent algorithm (iTableSMD). Within a broader multi-block variance reduction and inertial acceleration framework, we demonstrate the sublinear convergence rate for the subsequential sequence produced by the iTableSMD algorithm. We further show that iTableSMD requires at most O(ε^{-2}) iterations in expectation to attain an ε-stationary point and establish the global convergence of the sequence. Numerical experiments on real datasets demonstrate that our proposed algorithm is efficient and achieve better performance than the existing state-of-the-art methods. △ Less

Submitted 24 February, 2024; originally announced February 2024.

Spectral Properties of Dual Unit Gain Graphs

Authors: Chunfeng Cui, Yong Lu, Liqun Qi, Ligong Wang

Abstract: In this paper, we study dual quaternion and dual complex unit gain graphs and their spectral properties in a unified frame of dual unit gain graphs. Unit dual quaternions represent rigid movements in the 3D space, and have wide applications in robotics and computer graphics. Dual complex numbers found application in brain science recently. We establish the interlacing theorem for dual unit gain gr… ▽ More In this paper, we study dual quaternion and dual complex unit gain graphs and their spectral properties in a unified frame of dual unit gain graphs. Unit dual quaternions represent rigid movements in the 3D space, and have wide applications in robotics and computer graphics. Dual complex numbers found application in brain science recently. We establish the interlacing theorem for dual unit gain graphs, and show that the spectral radius of a dual unit gain graph is always not greater than the spectral radius of the underlying graph, and these two radii are equal if and only if the dual gain graph is balanced. By using the dual cosine functions, we establish the closed form of eigenvalues of adjacency and Laplacian matrices of dual complex and quaternion unit gain cycles. We then show the coefficient theorem holds for dual unit gain graphs. Similar results hold for the spectral radius of the Laplacian matrix of the dual unit gain graph too. △ Less

Submitted 7 May, 2024; v1 submitted 20 February, 2024; originally announced February 2024.

Dual Quaternion Laplacian Matrix and Formation Control

Authors: Liqun Qi, Chunfeng Cui

Abstract: The dual quaternion Laplacian matrix of desired relative configurations in multi-agent formation control is similar to the classical unweighted Laplacian matrix via a dual quaternion diagonal unitary matrix. Its eigenvalues are all positive numbers except one zero eigenvalue. A unit dual quaternion vector is a desired formation vector if and only if it is in the null space of this dual quaternion… ▽ More The dual quaternion Laplacian matrix of desired relative configurations in multi-agent formation control is similar to the classical unweighted Laplacian matrix via a dual quaternion diagonal unitary matrix. Its eigenvalues are all positive numbers except one zero eigenvalue. A unit dual quaternion vector is a desired formation vector if and only if it is in the null space of this dual quaternion Laplacian matrix. We study a control law based upon dual quaternion Laplacian. We extend our discussion to directed graphs. We also show that pairwise asymptotical stability can be reduced to rank-one asymptotical stability. △ Less

Submitted 18 January, 2024; v1 submitted 10 January, 2024; originally announced January 2024.

A Bregman Proximal Stochastic Gradient Method with Extrapolation for Nonconvex Nonsmooth Problems

Authors: Qingsong Wang, Zehui Liu, Chunfeng Cui, Deren Han

Abstract: In this paper, we explore a specific optimization problem that involves the combination of a differentiable nonconvex function and a nondifferentiable function. The differentiable component lacks a global Lipschitz continuous gradient, posing challenges for optimization. To address this issue and accelerate the convergence, we propose a Bregman proximal stochastic gradient method with extrapolatio… ▽ More In this paper, we explore a specific optimization problem that involves the combination of a differentiable nonconvex function and a nondifferentiable function. The differentiable component lacks a global Lipschitz continuous gradient, posing challenges for optimization. To address this issue and accelerate the convergence, we propose a Bregman proximal stochastic gradient method with extrapolation (BPSGE), which only requires smooth adaptivity of the differentiable part. Under the variance reduction framework, we not only analyze the subsequential and global convergence of the proposed algorithm under certain conditions, but also analyze the sublinear convergence rate of the subsequence, and the complexity of the algorithm, revealing that the BPSGE algorithm requires at most O(epsilon\^\,(-2)) iterations in expectation to attain an epsilon-stationary point. To validate the effectiveness of our proposed algorithm, we conduct numerical experiments on three real-world applications: graph regularized nonnegative matrix factorization (NMF), matrix factorization with weakly-convex regularization, and NMF with nonconvex sparsity constraints. These experiments demonstrate that BPSGE is faster than the baselines without extrapolation. △ Less

Submitted 3 January, 2024; originally announced January 2024.

Comments: accepted by AAAI 2024

A Genuine Extension of The Moore-Penrose Inverse to Dual Matrices

Authors: Chunfeng Cui, Liqun Qi

Abstract: The Moore-Penrose inverse is a genuine extension of the matrix inverse. Given a complex matrix, there uniquely exists another complex matrix satisfying the four Moore-Penrose conditions, and if the original matrix is nonsingular, it is exactly the inverse of that matrix. In the last one and half decade, in the study of approximate synthesis in kinematic, two generalizations of the Moore-Penrose in… ▽ More The Moore-Penrose inverse is a genuine extension of the matrix inverse. Given a complex matrix, there uniquely exists another complex matrix satisfying the four Moore-Penrose conditions, and if the original matrix is nonsingular, it is exactly the inverse of that matrix. In the last one and half decade, in the study of approximate synthesis in kinematic, two generalizations of the Moore-Penrose inverse appeared for dual real matrices,including Moore-Penrose dual generalized inverse and dual Moore-Penrose generalized inverse (DMPGI). DMPGI satisfies the four Moore-Penrose conditions, but does not exist for uncountably many dual real matrices. %Another generalization, called Moore-Penrose dual generalized inverse (MPDGI), is different from DMPGI even if DMPGI exists. In this paper, based upon the singular value decomposition of dual matrices, we extend the first Moore-Penrose condition to dual matrices and introduce a genuine extension of the Moore-Penrose inverse to dual matrices, referred to as GMPI. Given a dual complex matrix, its GMPI is the unique dual complex matrix which satisfy the first extended and the other three Moore-Penrose conditions. If the original matrix is a complex matrix, its GMPI is exactly the Moore-Penrose inverse of that matrix. And if the original matrix is a dual real matrix and its DMPGI exists, its GMPI coincides with its DMPGI. △ Less

Submitted 31 July, 2023; originally announced July 2023.

Dual Number Matrices with Primitive and Irreducible Nonnegative Standard Parts

Authors: Liqun Qi, Chunfeng Cui

Abstract: In this paper, we extend the Perron-Frobenius theory to dual number matrices with primitive and irreducible nonnegative standard parts. One motivation of our research is to consider probabilities as well as perturbation, or error bounds, or variances, in the Markov chain process. We show that such a dual number matrix always has a positive dual number eigenvalue with a positive dual number eigenve… ▽ More In this paper, we extend the Perron-Frobenius theory to dual number matrices with primitive and irreducible nonnegative standard parts. One motivation of our research is to consider probabilities as well as perturbation, or error bounds, or variances, in the Markov chain process. We show that such a dual number matrix always has a positive dual number eigenvalue with a positive dual number eigenvector. The standard part of this positive dual number eigenvalue is larger than or equal to the modulus of the standard part of any other eigenvalue of this dual number matrix. We present an explicit formula to compute the dual part of this positive dual number eigenvalue. The Collatz minimax theorem also holds here.The results are nontrivial as even a positive dual number matrix may have no eigenvalue at all. An algorithm based upon the Collatz minimax theorem is constructed. The convergence of the algorithm is studied. We show the upper bounds on the distance of stationary states between the dual Markov chain and the perturbed Markov chain. Numerical results on both synthetic examples and dual Markov chain including some real world examples are reported. △ Less

Submitted 6 July, 2023; v1 submitted 28 June, 2023; originally announced June 2023.

Eigenvalues and Jordan Forms of Dual Complex Matrices

Authors: Liqun Qi, Chunfeng Cui

Abstract: Dual complex matrices have found applications in brain science. There are two different definitions of the dual complex number multiplication. One is noncommutative. Another is commutative. In this paper, we use the commutative definition. This definition is used in the research related with brain science. Under this definition, eigenvalues of dual complex matrices are defined. However, there ar… ▽ More Dual complex matrices have found applications in brain science. There are two different definitions of the dual complex number multiplication. One is noncommutative. Another is commutative. In this paper, we use the commutative definition. This definition is used in the research related with brain science. Under this definition, eigenvalues of dual complex matrices are defined. However, there are cases of dual complex matrices which have no eigenvalues or have infinitely many eigenvalues. We show that an $n \times n$ dual complex matrix is diagonalizable if and only if it has exactly $n$ eigenvalues with $n$ appreciably linearly independent eigenvectors. Hermitian dual complex matrices are diagonalizable. We present the Jordan form of a dual complex matrix with a diagonalizable standard part, and the Jordan form of a dual complex matrix with a Jordan block standard part. Based on these, we give a description of the eigenvalues of a general square dual complex matrix. △ Less

Submitted 22 June, 2023; v1 submitted 27 May, 2023; originally announced June 2023.

A Power Method for Computing the Dominant Eigenvalue of a Dual Quaternion Hermitian Matrix

Authors: Chunfeng Cui, Liqun Qi

Abstract: In this paper, we first study the projections onto the set of unit dual quaternions, and the set of dual quaternion vectors with unit norms. Then we propose a power method for computing the dominant eigenvalue of a dual quaternion Hermitian matrix. For a strict dominant eigenvalue, we show the sequence generated by the power method converges to the dominant eigenvalue and its corresponding eigenve… ▽ More In this paper, we first study the projections onto the set of unit dual quaternions, and the set of dual quaternion vectors with unit norms. Then we propose a power method for computing the dominant eigenvalue of a dual quaternion Hermitian matrix. For a strict dominant eigenvalue, we show the sequence generated by the power method converges to the dominant eigenvalue and its corresponding eigenvector linearly. For a general dominant eigenvalue, we show the standard part of the sequence generated by the power method converges to the standard part of the dominant eigenvalue and its corresponding eigenvector linearly. Based upon these, we reformulate the simultaneous localization and mapping (SLAM) problem as a rank-one dual quaternion completion problem. A two-block coordinate descent method is proposed to solve this problem. One block has a closed-form solution and the other block is the best rank-one approximation problem of a dual quaternion Hermitian matrix, which can be computed by the power method. Numerical experiments are presented to show the efficiency of our proposed power method. △ Less

Submitted 1 May, 2023; v1 submitted 9 April, 2023; originally announced April 2023.

Comments: 32 pages, 3 figures

MSC Class: 15B33; 15A18; 68T40

Improving the generalization via coupled tensor norm regularization

Authors: Ying Gao, Yunfei Qu, Chunfeng Cui, Deren Han

Abstract: In this paper, we propose a coupled tensor norm regularization that could enable the model output feature and the data input to lie in a low-dimensional manifold, which helps us to reduce overfitting. We show this regularization term is convex, differentiable, and gradient Lipschitz continuous for logistic regression, while nonconvex and nonsmooth for deep neural networks. We further analyze the c… ▽ More In this paper, we propose a coupled tensor norm regularization that could enable the model output feature and the data input to lie in a low-dimensional manifold, which helps us to reduce overfitting. We show this regularization term is convex, differentiable, and gradient Lipschitz continuous for logistic regression, while nonconvex and nonsmooth for deep neural networks. We further analyze the convergence of the first-order method for solving this model. The numerical experiments demonstrate that our method is efficient. △ Less

Submitted 22 February, 2023; originally announced February 2023.

Comments: Operations Research Letters

Augmented Quaternion and Augmented Unit Quaternion Optimization

Authors: Liqun Qi, Xiangke Wang, Chunfeng Cui

Abstract: In this paper, we introduce and explore augmented quaternions and augmented unit quaternions, and present an augmented unit quaternion optimization model. An augmented quaternion consist of a quaternion and a translation vector. The multiplication rule of augmented quaternion is defined. An augmented unit quaternion consists of a unit quaternion and a translation vector. The augmented unit quatern… ▽ More In this paper, we introduce and explore augmented quaternions and augmented unit quaternions, and present an augmented unit quaternion optimization model. An augmented quaternion consist of a quaternion and a translation vector. The multiplication rule of augmented quaternion is defined. An augmented unit quaternion consists of a unit quaternion and a translation vector. The augmented unit quaternions form a Lie group. By means of augmented unit quaternions, we study the error model and kinematics. Then we formulate two classical problems in robot research, i.e., the hand-eye calibration problem and the simultaneous localization and mapping (SLAM) problem as augmented unit quaternion optimization problems, which are actually real smooth spherical equality constrained optimization problems. Comparing with the corresponding unit dual quaternion optimization model, the augmented unit quaternion optimization model has less variables and removes the orthogonality constraints. △ Less

Submitted 27 February, 2023; v1 submitted 9 January, 2023; originally announced January 2023.

Generalizing and Improving Jacobian and Hessian Regularization

Authors: Chenwei Cui, Zehao Yan, Guangshen Liu, Liangfu Lu

Abstract: Jacobian and Hessian regularization aim to reduce the magnitude of the first and second-order partial derivatives with respect to neural network inputs, and they are predominantly used to ensure the adversarial robustness of image classifiers. In this work, we generalize previous efforts by extending the target matrix from zero to any matrix that admits efficient matrix-vector products. The propos… ▽ More Jacobian and Hessian regularization aim to reduce the magnitude of the first and second-order partial derivatives with respect to neural network inputs, and they are predominantly used to ensure the adversarial robustness of image classifiers. In this work, we generalize previous efforts by extending the target matrix from zero to any matrix that admits efficient matrix-vector products. The proposed paradigm allows us to construct novel regularization terms that enforce symmetry or diagonality on square Jacobian and Hessian matrices. On the other hand, the major challenge for Jacobian and Hessian regularization has been high computational complexity. We introduce Lanczos-based spectral norm minimization to tackle this difficulty. This technique uses a parallelized implementation of the Lanczos algorithm and is capable of effective and stable regularization of large Jacobian and Hessian matrices. Theoretical justifications and empirical evidence are provided for the proposed paradigm and technique. We carry out exploratory experiments to validate the effectiveness of our novel regularization terms. We also conduct comparative experiments to evaluate Lanczos-based spectral norm minimization against prior methods. Results show that the proposed methodologies are advantageous for a wide range of tasks. △ Less

Submitted 1 December, 2022; originally announced December 2022.

Comments: Under review by AISTATS 2023

Fourier Neural Solver for large sparse linear algebraic systems

Authors: Chen Cui, Kai Jiang, Yun Liu, Shi Shu

Abstract: Large sparse linear algebraic systems can be found in a variety of scientific and engineering fields, and many scientists strive to solve them in an efficient and robust manner. In this paper, we propose an interpretable neural solver, the Fourier Neural Solver (FNS), to address them. FNS is based on deep learning and Fast Fourier transform. Because the error between the iterative solution and the… ▽ More Large sparse linear algebraic systems can be found in a variety of scientific and engineering fields, and many scientists strive to solve them in an efficient and robust manner. In this paper, we propose an interpretable neural solver, the Fourier Neural Solver (FNS), to address them. FNS is based on deep learning and Fast Fourier transform. Because the error between the iterative solution and the ground truth involves a wide range of frequency modes, FNS combines a stationary iterative method and frequency space correction to eliminate different components of the error. Local Fourier analysis reveals that the FNS can pick up on the error components in frequency space that are challenging to eliminate with stationary methods. Numerical experiments on the anisotropy diffusion equation, convection-diffusion equation, and Helmholtz equation show that FNS is more efficient and more robust than the state-of-the-art neural solver. △ Less

Submitted 7 October, 2022; originally announced October 2022.

Comments: 15 pages, 10 figures

MSC Class: 65F10 65N22 68T07 35Q68

Dual $r$-Rank Decomposition and Its Applications

Authors: Hongxing Wang, Chong Cui, Xiaoji Liu

Abstract: In this paper, we introduce the dual $r$-rank decomposition of dual matrix, get its existence condition and equivalent form of the decomposition, as well as derive some characterizations of dual Moore-Penrose generalized inverse(DMPGI). Based on DMPGI, we introduce one special dual matrix(dual EP matrix). By applying the dual $r$-rank decomposition we derive several characterizations of dual EP ma… ▽ More In this paper, we introduce the dual $r$-rank decomposition of dual matrix, get its existence condition and equivalent form of the decomposition, as well as derive some characterizations of dual Moore-Penrose generalized inverse(DMPGI). Based on DMPGI, we introduce one special dual matrix(dual EP matrix). By applying the dual $r$-rank decomposition we derive several characterizations of dual EP matrix, dual idempotent matrix, dual generalized inverses, and the relationships among dual Penrose equations. △ Less

Submitted 6 May, 2022; v1 submitted 20 April, 2022; originally announced April 2022.

MSC Class: 15A09

Optimization Models and Interpretations for Three Types of Adversarial Perturbations against Support Vector Machines

Authors: Wen Su, Qingna Li, Chunfeng Cui

Abstract: Adversarial perturbations have drawn great attentions in various deep neural networks. Most of them are computed by iterations and cannot be interpreted very well. In contrast, little attentions are paid to basic machine learning models such as support vector machines. In this paper, we investigate the optimization models and the interpretations for three types of adversarial perturbations against… ▽ More Adversarial perturbations have drawn great attentions in various deep neural networks. Most of them are computed by iterations and cannot be interpreted very well. In contrast, little attentions are paid to basic machine learning models such as support vector machines. In this paper, we investigate the optimization models and the interpretations for three types of adversarial perturbations against support vector machines, including sample-adversarial perturbations (sAP), class-universal adversarial perturbations (cuAP) as well as universal adversarial perturbations (uAP). For linear binary/multi classification support vector machines (SVMs), we derive the explicit solutions for sAP, cuAP and uAP (binary case), and approximate solution for uAP of multi-classification. We also obtain the upper bound of fooling rate for uAP. Such results not only increase the interpretability of the three adversarial perturbations, but also provide great convenience in computation since iterative process can be avoided. Numerical results show that our method is fast and effective in calculating three types of adversarial perturbations. △ Less

Submitted 6 April, 2022; originally announced April 2022.

Solving time-dependent parametric PDEs by multiclass classification-based reduced order model

Authors: Chen Cui, Kai Jiang, Shi Shu

Abstract: In this paper, we propose a network model, the multiclass classification-based reduced order model (MC-ROM), for solving time-dependent parametric partial differential equations (PPDEs). This work is inspired by the observation of applying the deep learning-based reduced order model (DL-ROM) to solve diffusion-dominant PPDEs. We find that the DL-ROM has a good approximation for some special model… ▽ More In this paper, we propose a network model, the multiclass classification-based reduced order model (MC-ROM), for solving time-dependent parametric partial differential equations (PPDEs). This work is inspired by the observation of applying the deep learning-based reduced order model (DL-ROM) to solve diffusion-dominant PPDEs. We find that the DL-ROM has a good approximation for some special model parameters, but it cannot approximate the drastic changes of the solution as time evolves. Based on this fact, we classify the dataset according to the magnitude of the solutions and construct corresponding subnets dependent on different types of data. Then we train a classifier to integrate different subnets together to obtain the MC-ROM. When subsets have the same architecture, we can use transfer learning techniques to accelerate offline training. Numerical experiments show that the MC-ROM improves the generalization ability of the DL-ROM both for diffusion- and convection-dominant problems, and maintains the DL-ROM's advantage of good approximation ability. We also compare the approximation accuracy and computational efficiency of the proper orthogonal decomposition (POD) which is not suitable for convection-dominant problems. For diffusion-dominant problems, the MC-ROM has better approximation accuracy than the POD in a small dimensionality reduction space, and its computational performance is more efficient than the POD. △ Less

Submitted 7 October, 2022; v1 submitted 11 November, 2021; originally announced November 2021.

Comments: 20 pages, 16 figures

Directional FDR Control for Sub-Gaussian Sparse GLMs

Authors: Chang Cui, Jinzhu Jia, Yijun Xiao, Huiming Zhang

Abstract: High-dimensional sparse generalized linear models (GLMs) have emerged in the setting that the number of samples and the dimension of variables are large, and even the dimension of variables grows faster than the number of samples. False discovery rate (FDR) control aims to identify some small number of statistically significantly nonzero results after getting the sparse penalized estimation of GLM… ▽ More High-dimensional sparse generalized linear models (GLMs) have emerged in the setting that the number of samples and the dimension of variables are large, and even the dimension of variables grows faster than the number of samples. False discovery rate (FDR) control aims to identify some small number of statistically significantly nonzero results after getting the sparse penalized estimation of GLMs. Using the CLIME method for precision matrix estimations, we construct the debiased-Lasso estimator and prove the asymptotical normality by minimax-rate oracle inequalities for sparse GLMs. In practice, it is often needed to accurately judge each regression coefficient's positivity and negativity, which determines whether the predictor variable is positively or negatively related to the response variable conditionally on the rest variables. Using the debiased estimator, we establish multiple testing procedures. Under mild conditions, we show that the proposed debiased statistics can asymptotically control the directional (sign) FDR and directional false discovery variables at a pre-specified significance level. Moreover, it can be shown that our multiple testing procedure can approximately achieve a statistical power of 1. We also extend our methods to the two-sample problems and propose the two-sample test statistics. Under suitable conditions, we can asymptotically achieve directional FDR control and directional FDV control at the specified significance level for two-sample problems. Some numerical simulations have successfully verified the FDR control effects of our proposed testing procedures, which sometimes outperforms the classical knockoff method. △ Less

Submitted 2 May, 2021; originally announced May 2021.

Comments: 37 pages

Condensed Generalized Finite Element Method (CGFEM)

Authors: Qinghui Zhang, Cu Cui

Abstract: Generalized or extended finite element methods (GFEM/XFEM) are in general badly conditioned and have numerous additional degrees of freedom (DOF) compared with the FEM because of introduction of enriched functions. In this paper, we develop an approach to establish a subspace of a conventional GFEM/XFEM approximation space using partition of unity (PU) techniques and local least square procedures.… ▽ More Generalized or extended finite element methods (GFEM/XFEM) are in general badly conditioned and have numerous additional degrees of freedom (DOF) compared with the FEM because of introduction of enriched functions. In this paper, we develop an approach to establish a subspace of a conventional GFEM/XFEM approximation space using partition of unity (PU) techniques and local least square procedures. The proposed GFEM is referred to as condensed GFEM (CGFEM), which (i) possesses as many DOFs as the preliminary FEM, (ii) enjoys similar approximation properties with the GFEM/XFEM, and (iii) is well-conditioned in a sense that its conditioning is of the same order as that of the FEM. The fundamental approximation properties of CGFEM is proven mathematically. The CGFEM is applied to a problem of high order polynomial approximations and a Poisson crack problem; optimal convergence orders of the former are proven rigorously. The numerical experiments and comparisons with the conventional GFEM/XFEM and FEM are made to verify the theory and effectiveness of CGFEM. △ Less

Submitted 2 February, 2020; originally announced February 2020.

Active Subspace of Neural Networks: Structural Analysis and Universal Attacks

Authors: Chunfeng Cui, Kaiqi Zhang, Talgat Daulbaev, Julia Gusak, Ivan Oseledets, Zheng Zhang

Abstract: Active subspace is a model reduction method widely used in the uncertainty quantification community. In this paper, we propose analyzing the internal structure and vulnerability and deep neural networks using active subspace. Firstly, we employ the active subspace to measure the number of "active neurons" at each intermediate layer and reduce the number of neurons from several thousands to several… ▽ More Active subspace is a model reduction method widely used in the uncertainty quantification community. In this paper, we propose analyzing the internal structure and vulnerability and deep neural networks using active subspace. Firstly, we employ the active subspace to measure the number of "active neurons" at each intermediate layer and reduce the number of neurons from several thousands to several dozens. This motivates us to change the network structure and to develop a new and more compact network, referred to as {ASNet}, that has significantly fewer model parameters. Secondly, we propose analyzing the vulnerability of a neural network using active subspace and finding an additive universal adversarial attack vector that can misclassify a dataset with a high probability. Our experiments on CIFAR-10 show that ASNet can achieve 23.98$\times$ parameter and 7.30$\times$ flops reduction. The universal active subspace attack vector can achieve around 20% higher attack ratio compared with the existing approach in all of our numerical experiments. The PyTorch codes for this paper are available online. △ Less

Submitted 29 April, 2020; v1 submitted 28 October, 2019; originally announced October 2019.

Tensor Methods for Generating Compact Uncertainty Quantification and Deep Learning Models

Authors: Chunfeng Cui, Cole Hawkins, Zheng Zhang

Abstract: Tensor methods have become a promising tool to solve high-dimensional problems in the big data era. By exploiting possible low-rank tensor factorization, many high-dimensional model-based or data-driven problems can be solved to facilitate decision making or machine learning. In this paper, we summarize the recent applications of tensor computation in obtaining compact models for uncertainty quant… ▽ More Tensor methods have become a promising tool to solve high-dimensional problems in the big data era. By exploiting possible low-rank tensor factorization, many high-dimensional model-based or data-driven problems can be solved to facilitate decision making or machine learning. In this paper, we summarize the recent applications of tensor computation in obtaining compact models for uncertainty quantification and deep learning. In uncertainty analysis where obtaining data samples is expensive, we show how tensor methods can significantly reduce the simulation or measurement cost. To enable the deployment of deep learning on resource-constrained hardware platforms, tensor methods can be used to significantly compress an over-parameterized neural network model or directly train a small-size model from scratch via optimization or statistical techniques. Recent Bayesian tensorized neural networks can automatically determine their tensor ranks in the training process. △ Less

Submitted 20 August, 2019; originally announced August 2019.

Chance-Constrained and Yield-aware Optimization of Photonic ICs with Non-Gaussian Correlated Process Variations

Authors: Chunfeng Cui, Kaikai Liu, Zheng Zhang

Abstract: Uncertainty quantification has become an efficient tool for uncertainty-aware prediction, but its power in yield-aware optimization has not been well explored from either theoretical or application perspectives. Yield optimization is a much more challenging task. On one side, optimizing the generally non-convex probability measure of performance metrics is difficult. On the other side, evaluating… ▽ More Uncertainty quantification has become an efficient tool for uncertainty-aware prediction, but its power in yield-aware optimization has not been well explored from either theoretical or application perspectives. Yield optimization is a much more challenging task. On one side, optimizing the generally non-convex probability measure of performance metrics is difficult. On the other side, evaluating the probability measure in each optimization iteration requires massive simulation data, especially when the process variations are non-Gaussian correlated. This paper proposes a data-efficient framework for the yield-aware optimization of photonic ICs. This framework optimizes the design performance with a yield guarantee, and it consists of two modules: a modeling module that builds stochastic surrogate models for design objectives and chance constraints with a few simulation samples, and a novel yield optimization module that handles probabilistic objectives and chance constraints in an efficient deterministic way. This deterministic treatment avoids repeatedly evaluating probability measures at each iteration, thus it only requires a few simulations in the whole optimization flow. We validate the accuracy and efficiency of the whole framework by a synthetic example and two photonic ICs. Our optimization method can achieve more than $30\times$ reduction of simulation cost and better design performance on the test cases compared with a Bayesian yield optimization approach developed recently. △ Less

Submitted 24 April, 2020; v1 submitted 20 August, 2019; originally announced August 2019.

Efficient Uncertainty Modeling for System Design via Mixed Integer Programming

Authors: Zichang He, Weilong Cui, Chunfeng Cui, Timothy Sherwood, Zheng Zhang

Abstract: The post-Moore era casts a shadow of uncertainty on many aspects of computer system design. Managing that uncertainty requires new algorithmic tools to make quantitative assessments. While prior uncertainty quantification methods, such as generalized polynomial chaos (gPC), show how to work precisely under the uncertainty inherent to physical devices, these approaches focus solely on variables fro… ▽ More The post-Moore era casts a shadow of uncertainty on many aspects of computer system design. Managing that uncertainty requires new algorithmic tools to make quantitative assessments. While prior uncertainty quantification methods, such as generalized polynomial chaos (gPC), show how to work precisely under the uncertainty inherent to physical devices, these approaches focus solely on variables from a continuous domain. However, as one moves up the system stack to the architecture level many parameters are constrained to a discrete (integer) domain. This paper proposes an efficient and accurate uncertainty modeling technique, named mixed generalized polynomial chaos (M-gPC), for architectural uncertainty analysis. The M-gPC technique extends the generalized polynomial chaos (gPC) theory originally developed in the uncertainty quantification community, such that it can efficiently handle the mixed-type (i.e., both continuous and discrete) uncertainties in computer architecture design. Specifically, we employ some stochastic basis functions to capture the architecture-level impact caused by uncertain parameters in a simulator. We also develop a novel mixed-integer programming method to select a small number of uncertain parameter samples for detailed simulations. With a few highly informative simulation samples, an accurate surrogate model is constructed in place of cycle-level simulators for various architectural uncertainty analysis. In the chip-multiprocessor (CMP) model, we are able to estimate the propagated uncertainties with only 95 samples whereas Monte Carlo requires 5*10^4 samples to achieve the similar accuracy. We also demonstrate the efficiency and effectiveness of our method on a detailed DRAM subsystem. △ Less

Submitted 20 October, 2019; v1 submitted 10 July, 2019; originally announced July 2019.

Comments: International Conf. Computer Aided Design (ICCAD), 2019

High-Dimensional Uncertainty Quantification of Electronic and Photonic IC with Non-Gaussian Correlated Process Variations

Authors: Chunfeng Cui, Zheng Zhang

Abstract: Uncertainty quantification based on generalized polynomial chaos has been used in many applications. It has also achieved great success in variation-aware design automation. However, almost all existing techniques assume that the parameters are mutually independent or Gaussian correlated, which is rarely true in real applications. For instance, in chip manufacturing, many process variations are ac… ▽ More Uncertainty quantification based on generalized polynomial chaos has been used in many applications. It has also achieved great success in variation-aware design automation. However, almost all existing techniques assume that the parameters are mutually independent or Gaussian correlated, which is rarely true in real applications. For instance, in chip manufacturing, many process variations are actually correlated. Recently, some techniques have been developed to handle non-Gaussian correlated random parameters, but they are time-consuming for high-dimensional problems. We present a new framework to solve uncertainty quantification problems with many non-Gaussian correlated uncertainties. Firstly, we propose a set of smooth basis functions to well capture the impact of non-Gaussian correlated process variations. We develop a tensor approach to compute these basis functions in a high-dimension setting. Secondly, we investigate the theoretical aspect and practical implementation of a sparse solver to compute the coefficients of all basis functions. We provide some theoretical analysis for the exact recovery condition and error bound of this sparse solver in the context of uncertainty quantification. We present three adaptive sampling approaches to improve the performance of the sparse solver. Finally, we validate our methods by synthetic and practical electronic/photonic ICs with 19 to 57 non-Gaussian correlated variation parameters. Our approach outperforms Monte Carlo by thousands of times in terms of efficiency. It can also accurately predict the output density functions with multiple peaks caused by non-Gaussian correlations, which are hard to capture by existing methods. △ Less

Submitted 20 June, 2019; v1 submitted 30 January, 2019; originally announced February 2019.

Comments: arXiv admin note: substantial text overlap with arXiv:1807.01778

Stochastic Collocation with Non-Gaussian Correlated Process Variations: Theory, Algorithms and Applications

Authors: Chunfeng Cui, Zheng Zhang

Abstract: Stochastic spectral methods have achieved great success in the uncertainty quantification of many engineering problems, including electronic and photonic integrated circuits influenced by fabrication process variations. Existing techniques employ a generalized polynomial-chaos expansion, and they almost always assume that all random parameters are mutually independent or Gaussian correlated. Howev… ▽ More Stochastic spectral methods have achieved great success in the uncertainty quantification of many engineering problems, including electronic and photonic integrated circuits influenced by fabrication process variations. Existing techniques employ a generalized polynomial-chaos expansion, and they almost always assume that all random parameters are mutually independent or Gaussian correlated. However, this assumption is rarely true in real applications. How to handle non-Gaussian correlated random parameters is a long-standing and fundamental challenge. A main bottleneck is the lack of theory and computational methods to perform a projection step in a correlated uncertain parameter space. This paper presents an optimization-based approach to automatically determinate the quadrature nodes and weights required in a projection step, and develops an efficient stochastic collocation algorithm for systems with non-Gaussian correlated parameters. We also provide some theoretical proofs for the complexity and error bound of our proposed method. Numerical experiments on synthetic, electronic and photonic integrated circuit examples show the nearly exponential convergence rate and excellent efficiency of our proposed approach. Many other challenging uncertainty-related problems can be further solved based on this work. △ Less

Submitted 5 December, 2018; v1 submitted 29 August, 2018; originally announced August 2018.

Comments: 14 pages,11 figure. 4 tables

Stochastic Collocation with Non-Gaussian Correlated Parameters via a New Quadrature Rule

Authors: Chunfeng Cui, Zheng Zhang

Abstract: This paper generalizes stochastic collocation methods to handle correlated non-Gaussian random parameters. The key challenge is to perform a multivariate numerical integration in a correlated parameter space when computing the coefficient of each basis function via a projection step. We propose an optimization model and a block coordinate descent solver to compute the required quadrature samples.… ▽ More This paper generalizes stochastic collocation methods to handle correlated non-Gaussian random parameters. The key challenge is to perform a multivariate numerical integration in a correlated parameter space when computing the coefficient of each basis function via a projection step. We propose an optimization model and a block coordinate descent solver to compute the required quadrature samples. Our method is verified with a CMOS ring oscillator and an optical ring resonator, showing 3000x speedup over Monte Carlo. △ Less

Submitted 25 August, 2018; originally announced August 2018.

Comments: 3 pages, 5 figure, EPEPS 2018

Uncertainty Quantification of Electronic and Photonic ICs with Non-Gaussian Correlated Process Variations

Authors: Chunfeng Cui, Zheng Zhang

Abstract: Since the invention of generalized polynomial chaos in 2002, uncertainty quantification has impacted many engineering fields, including variation-aware design automation of integrated circuits and integrated photonics. Due to the fast convergence rate, the generalized polynomial chaos expansion has achieved orders-of-magnitude speedup than Monte Carlo in many applications. However, almost all exis… ▽ More Since the invention of generalized polynomial chaos in 2002, uncertainty quantification has impacted many engineering fields, including variation-aware design automation of integrated circuits and integrated photonics. Due to the fast convergence rate, the generalized polynomial chaos expansion has achieved orders-of-magnitude speedup than Monte Carlo in many applications. However, almost all existing generalized polynomial chaos methods have a strong assumption: the uncertain parameters are mutually independent or Gaussian correlated. This assumption rarely holds in many realistic applications, and it has been a long-standing challenge for both theorists and practitioners. This paper propose a rigorous and efficient solution to address the challenge of non-Gaussian correlation. We first extend generalized polynomial chaos, and propose a class of smooth basis functions to efficiently handle non-Gaussian correlations. Then, we consider high-dimensional parameters, and develop a scalable tensor method to compute the proposed basis functions. Finally, we develop a sparse solver with adaptive sample selections to solve high-dimensional uncertainty quantification problems. We validate our theory and algorithm by electronic and photonic ICs with 19 to 57 non-Gaussian correlated variation parameters. The results show that our approach outperforms Monte Carlo by $2500\times$ to $3000\times$ in terms of efficiency. Moreover, our method can accurately predict the output density functions with multiple peaks caused by non-Gaussian correlations, which is hard to handle by existing methods. Based on the results in this paper, many novel uncertainty quantification algorithms can be developed and can be further applied to a broad range of engineering domains. △ Less

Submitted 30 June, 2018; originally announced July 2018.

A Quadratic Penalty Method for Hypergraph Matching

Authors: Chunfeng Cui, Qingna Li, Liqun Qi, Hong Yan

Abstract: Hypergraph matching is a fundamental problem in computer vision. Mathematically speaking, it maximizes a polynomial objective function, subject to assignment constraints. In this paper, we reformulate the hypergraph matching problem as a sparse constrained tensor optimization problem. The optimality conditions are characterized based on the sparse constrained optimization theory. By dropping the s… ▽ More Hypergraph matching is a fundamental problem in computer vision. Mathematically speaking, it maximizes a polynomial objective function, subject to assignment constraints. In this paper, we reformulate the hypergraph matching problem as a sparse constrained tensor optimization problem. The optimality conditions are characterized based on the sparse constrained optimization theory. By dropping the sparsity constraint, we show that the resulting relaxation problem can recover the global minimizer of the original problem. The critical step in solving the original problem is to identify the location of nonzero entries (referred as support set) in a global minimizer. Inspired by such observations, we penalize the equality constraints and apply the quadratic penalty method to solve the relaxation problem. Under reasonable assumptions, we show that the support set of the global minimizer in hypergraph matching problem can be correctly identified when the number of iterations is sufficiently large. A projected gradient method is applied as a subsolver to solve the quadratic penalty subproblem. Numerical results demonstrate that the exact recovery of support set indeed happens, and the proposed algorithms are efficient in terms of both accuracy and speed. △ Less

Submitted 13 November, 2017; v1 submitted 15 April, 2017; originally announced April 2017.

MSC Class: 65K05; 05C70; 15A69

Computing The Analytic Connectivity of A Uniform Hypergraph

Authors: Chufeng Cui, Ziyan Luo, Liqun Qi, Hong Yan

Abstract: The analytic connectivity, proposed as a substitute of the algebraic connectivity in the setting of hypergraphs, is an important quantity in spectral hypergraph theory. The definition of the analytic connectivity for a uniform hypergraph involves a series of optimization problems (POPs) associated with the Laplacian tensor of the hypergraph with nonnegativity constraints and a sphere constraint, w… ▽ More The analytic connectivity, proposed as a substitute of the algebraic connectivity in the setting of hypergraphs, is an important quantity in spectral hypergraph theory. The definition of the analytic connectivity for a uniform hypergraph involves a series of optimization problems (POPs) associated with the Laplacian tensor of the hypergraph with nonnegativity constraints and a sphere constraint, which poses difficulties in computation. To reduce the involved computation, properties on the algebraic connectivity are further exploited, and several important structured uniform hypergraphs are shown to attain their analytic connectivities at vertices of the minimum degrees, hence admit a relatively less computation by solving a small number of POPs. To efficiently solve each involved POP, we propose a feasible trust region algorithm ({\tt FTR}) by exploiting their special structures. The global convergence of {\tt FTR} to the second-order necessary conditions points is established, and numerical results for both small and large size examples with comparison to other existing algorithms for POPs are reported to demonstrate the efficiency of our proposed algorithm. △ Less

Submitted 4 November, 2016; originally announced November 2016.

All Real Eigenvalues of Symmetric Tensors

Authors: Chun-Feng Cui, Yu-Hong Dai, Jiawang Nie

Abstract: This paper studies how to compute all real eigenvalues of a symmetric tensor. As is well known, the largest or smallest eigenvalue can be found by solving a polynomial optimization problem, while the other middle eigenvalues can not. We propose a new approach for computing all real eigenvalues sequentially, from the largest to the smallest. It uses Jacobian SDP relaxations in polynomial optimizati… ▽ More This paper studies how to compute all real eigenvalues of a symmetric tensor. As is well known, the largest or smallest eigenvalue can be found by solving a polynomial optimization problem, while the other middle eigenvalues can not. We propose a new approach for computing all real eigenvalues sequentially, from the largest to the smallest. It uses Jacobian SDP relaxations in polynomial optimization. We show that each eigenvalue can be computed by solving a finite hierarchy of semidefinite relaxations. Numerical experiments are presented to show how to do this. △ Less

Submitted 13 December, 2014; v1 submitted 14 March, 2014; originally announced March 2014.