A Triangular Decomposition Algorithm for Differential Polynomial Systems with Elementary Computation Complexity

In this paper, a new triangular decomposition algorithm is proposed for ordinary differential polynomial systems, which has triple exponential computational complexity. The key idea is to eliminate one algebraic variable from a set of polynomials in one step using the theory of multivariate resultant. This seems to be the first differential triangular decomposition algorithm with elementary computation complexity.

Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems

Triangular decomposition with different properties has been used for various types of problem solving.In this paper,the concepts of pure chains and square-free pure triangular decomposition(SFPTD)of zero-dimensional polynomial systems are defined.Because of its good properties,SFPTD may be a key way to many problems related to zero-dimensional polynomial systems.Inspired by the work of Wang(2016)and of Dong and Mou(2019),the authors propose an algorithm for computing SFPTD based on Gr¨obner bases computation.The novelty of the algorithm is that the authors make use of saturated ideals and separant to ensure that the zero sets of any two pure chains are disjoint and every pure chain is square-free,respectively.On one hand,the authors prove the arithmetic complexity of the new algorithm can be single exponential in the square of the number of variables,which seems to be among the rare complexity analysis results for triangular-decomposition methods.On the other hand,the authors show experimentally that,on a large number of examples in the literature,the new algorithm is far more efficient than a popular triangular-decomposition method based on pseudodivision,and the methods based on SFPTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.

Direct linear discriminant analysis based on column pivoting QR decomposition and economic SVD

A direct linear discriminant analysis algorithm based on economic singular value decomposition （DLDA/ESVD） is proposed to address the computationally complex problem of the conventional DLDA algorithm, which directly uses ESVD to reduce dimension and extract eigenvectors corresponding to nonzero eigenvalues. Then a DLDA algorithm based on column pivoting orthogonal triangular （QR） decomposition and ESVD （DLDA/QR-ESVD） is proposed to improve the performance of the DLDA/ESVD algorithm by processing a high-dimensional low rank matrix, which uses column pivoting QR decomposition to reduce dimension and ESVD to extract eigenvectors corresponding to nonzero eigenvalues. The experimental results on ORL, FERET and YALE face databases show that the proposed two algorithms can achieve almost the same performance and outperform the conventional DLDA algorithm in terms of computational complexity and training time. In addition, the experimental results on random data matrices show that the DLDA/QR-ESVD algorithm achieves better performance than the DLDA/ESVD algorithm by processing high-dimensional low rank matrices.

Spectral Properties and Optimality for Elementary Matrices

A generalization of the Householder transformation,renamed as elementary matrix by A.S.Householder:Unitary transformation of a nonsymmetric matrix,J.ACM,5(4),339–342,1958,was introduced by LaBudde(Math Comput 17(84):433–437,1963)as a tool to obtain a tridiagonal matrix similar to a given square matrix.Some of the free parameters of the transformation can be chosen to attain better numerical properties.In this work,we study the spectral properties of the transformation.We also propose a special choice for free coefficients of that transformation to minimize its condition number.The transformation with such suitable choice of parameters is called optimal.