Search

We introduce the two‐sided Rayleigh quotient shift to the QR algorithm for non‐Hermitian matrices to achieve a cubic local convergence rate. For the singly shifted case, the two‐sided Rayleigh quotient iteration is incorporated into the QR iteration. A modified version of the method and its truncated version are developed to improve the efficiency. Based on the observation that the Francis double‐shift QR iteration is related to a 2D Grassmann–Rayleigh quotient iteration, A doubly shifted QR algorithm with the two‐sided 2D Grassmann–Rayleigh quotient double‐shift is proposed. A modified version of the method and its truncated version are also developed. Numerical examples are presented to show the convergence behavior of the proposed algorithms. Numerical examples also show that the truncated versions of the modified methods outperform their counterparts including the standard Rayleigh quotient single‐shift and the Francis double‐shift. [ABSTRACT FROM AUTHOR]

We generalize the recently proposed two‐sided Rayleigh quotient single‐shift and the two‐sided Grassmann–Rayleigh quotient double‐shift used in the QR algorithm and apply the generalized versions to the QZ algorithm. With such shift strategies the QZ algorithm normally has a cubic local convergence rate. Our main focus is on the modified shift strategies and their corresponding truncated versions. Numerical examples are provided to demonstrate the convergence properties and the efficiency of the QZ algorithm equipped with the proposed shifts. For the truncated versions, local convergence analysis is not provided. Numerical examples show they outperform the modified shifts and the standard Rayleigh quotient single‐shift and Francis double‐shift. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the complex roots of the polynomial system are represented as linear combinations of the roots of several univariate polynomial equations. An algorithm is proposed to compute such a representation for a given zero-dimensional polynomial equation system based on Gröbner basis computation. The main advantage of this representation is that the precision of the roots of the system can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for isolating the roots of the univariate equations in order to obtain roots of the polynomial system with a given precision. As a consequence, a root isolating algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation. [Copyright &y& Elsevier]

Abstract: Efficient characteristic set methods for computing zeros of polynomial equation systems in a finite field are proposed. The concept of proper triangular sets is introduced and an explicit formula for the number of zeros of a proper and monic triangular set is given. An improved zero decomposition algorithm is proposed to reduce the zero set of an equation system to the union of zero sets of monic proper triangular sets. The bitsize complexity of this algorithm is shown to be for Boolean polynomials, where is the number of variables and is the number of equations. We also give a multiplication free characteristic set method for Boolean polynomials, where the sizes of the polynomials occurred during the computation do not exceed the sizes of the input polynomials and the bitsize complexity of algorithm is for input polynomials with variables and degree . The algorithms are implemented in the case of Boolean polynomials and extensive experiments show that they are quite efficient for solving certain classes of Boolean equations raising from stream ciphers. [Copyright &y& Elsevier]

Abstract: In this paper we investigate structured backward errors for three kinds of generalized saddle point systems where the matrix is not symmetric and its block is not zero and has perturbations. Computable formula of backward errors are derived. The expressions are useful for testing the stability of practical algorithms. [Copyright &y& Elsevier]

Abstract: A backward error for inverse singular value problems with respect to an approximate solution is defined, and an explicit expression for the backward error is derived by extending the approach described in [J.G. Sun, Backward errors for the inverse eigenvalue problem, Numer. Math. 82 (1999) 339–349]. The expression may be useful for testing the stability of practical algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we present an algorithm to decompose ordinary non-linear difference polynomials with rational functions as coefficients. The algorithm provides an effective reduction of the decomposition of difference polynomials to the decomposition of linear difference polynomials over the same coefficient field. The algorithm is implemented in Maple for the constant coefficient case. Experimental results show that the algorithm is quite effective and can be used to decompose difference polynomials with thousands of terms. [Copyright &y& Elsevier]

Abstract: We present a complete numerical algorithm for isolating all the real zeros of a zero-dimensional triangular polynomial system . Our system is general, with no further assumptions. In particular, our algorithm successfully treats multiple zeros directly in such systems. A key idea is to introduce evaluation bounds and sleeve bounds. We also present a much more efficient algorithm for zero-dimensional triangular systems without multiple roots. We implemented our algorithms, and promising experimental results are shown. [Copyright &y& Elsevier]

Abstract: Given a multivariate quadratic polynomial system in a finite field , the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfying a non-degenerate quadratic equation is at least , where is the number of the variables in the equation. Consequently, the random assignment provides a polynomial-time approximation algorithm with approximation ratio for non-degenerate MAX-MQ. For large , the ratio is close to . According to a result by Håstad, it is NP-hard to approximate MAX-MQ with an approximation ratio of for a small positive number . Therefore, the minimal approximation ratio that can be achieved in polynomial time for MAX-MQ is . [Copyright &y& Elsevier]

Abstract: We prove several basic properties for difference ascending chains, including a necessary and sufficient condition for an ascending chain to be the characteristic set of its saturation ideal and a necessary and sufficient condition for an ascending chain to be the characteristic set of a reflexive prime ideal. Based on these properties, we propose an algorithm to decompose the zero set of a finite set of difference polynomials into the union of zero sets of certain ascending chains. This decomposition algorithm is implemented and used to solve the perfect ideal membership problem, and to prove certain difference identities automatically. [Copyright &y& Elsevier]

Abstract  In this paper, we present a complete algorithm to decompose nonlinear differential polynomials in one variable and with coefficients in a computable differential field $${\mathcal K}$$ of characteristic zero. The algorithm provides an efficient reduction of the problem to the factorization of LODOs over the same coefficient field. Besides arithmetic operations, the algorithm needs decomposition of algebraic polynomials, factorization of multi-variable polynomials, and solution of algebraic linear equation systems. The algorithm is implemented in Maple for the constant field case. The program can be used to decompose differential polynomials with thousands of terms effectively. [ABSTRACT FROM AUTHOR]

Abstract: We give a necessary and sufficient condition for an algebraic ODE to have a rational type general solution. For a first order autonomous ODE , we give an exact degree bound for its rational solutions, based on the connection between rational solutions of and rational parametrizations of the plane algebraic curve defined by . For a first order autonomous ODE, we further give a polynomial time algorithm for computing a rational general solution if it exists based on the computation of Laurent series solutions and Padé approximants. Experimental results show that the algorithm is quite efficient. [Copyright &y& Elsevier]

An algorithm is proposed to give a global approximation of an implicit real plane algebraic curve with rational quadratic B-spline curves. The algorithm consists of four steps: topology determination, curve segmentation, segment approximation and curve tracing. Due to the detailed geometric analysis, high accuracy of approximation may be achieved with a small number of quadratic segments. The final approximation keeps many important geometric features of the original curve such as the topology, convexity and sharp points. Our method is implemented and experiments show that it may achieve better approximation bound with less segments than previously known methods. We also extend the method to approximate spatial algebraic curves. [Copyright &y& Elsevier]

In this paper, we propose algorithms for the following problems in the implicitization of a set of differential rational parametric equations P. (1) To find a characteristic set for the implicit prime ideal of P. (2) To find a canonical representation for the image of P. (3) To decide whether the parameters of P are independent, and if not, to re-parameterize P so that the new parametric equations have independent parameters. (4) To compute the inversion maps of P, and as a consequence, to decide whether P is proper. If the implicit variety is of dimension one and P is not proper, to find a proper re-parameterization for P. [Copyright &y& Elsevier]

In this paper, we use two approaches to solve the Perspective-Three-Point (P3P) problem: the algebraic approach and the geometric approach. In the algebraic approach, we use Wu-Ritt's zero decomposition algorithm to give a complete triangular decomposition for the P3P equation system. This decomposition provides the first complete analytical solution to the P3P problem. We also give a complete solution classification for the P3P equation system, i.e., we give explicit criteria for the P3P problem to have one, two, three, and four solutions. Combining the analytical solutions with the criteria, we provide an algorithm, CASSC, which may be used to find complete and robust numerical solutions to the P3P problem. In the geometric approach, we give some pure geometric criteria for the number of real physical solutions. [ABSTRACT FROM AUTHOR]

In this paper, the concept of sparse difference resultant for a Laurent transformally essential system of difference polynomials is introduced and a simple criterion for the existence of sparse difference resultant is given. The concept of transformally homogenous polynomial is introduced and the sparse difference resultant is proved to be transformally homogenous. It is shown that the vanishing of the sparse difference resultant gives a necessary condition for the corresponding difference polynomial system to have non-zero solutions. Order and degree bounds for the sparse difference resultant are given. Based on these bounds, an algorithm to compute the sparse difference resultant is proposed, which is single exponential in terms of the number of variables, the Jacobi number, and the size of the Laurent transformally essential system. Furthermore, the precise order and degree, a determinant representation, and a Poisson-type product formula for the difference resultant are given. [ABSTRACT FROM AUTHOR]

In this paper, we first introduce the concept of Laurent differentially essential systems and give a criterion for a Laurent differential polynomial system to be Laurent differentially essential in terms of its support matrix. Then, the sparse differential resultant for a Laurent differentially essential system is defined, and its basic properties are proved. In particular, order and degree bounds for the sparse differential resultant are given. Based on these bounds, an algorithm to compute the sparse differential resultant is proposed, which is single exponential in terms of the Jacobi number and the size of the system. [ABSTRACT FROM AUTHOR]

We calculated the crustal stress field using the composite focal mechanism method based on the P-wave initial motion polarity data of the Tengchong volcanic area from January 2011 to April 2019 obtained from the Bulletin of Seismological Observations of Chinese stations. The magnitude range of earthquakes used in this study is 0–4, and their magnitudes are mainly approximately 1.0. To investigate the influence of the source location on the stress field and obtain reliable stress fields of the study area, we applied the double-difference algorithm to relocate the seismic events, obtaining more accurate and reliable relative positions of seismic events with a clearer seismic belt. On the basis of relocation results, the study on the stress field along the fault zone was conducted, and the influence of seismic event position on the stress field was analyzed. Results show that, first, the current stress regime in the shallow crust of the Tengchong volcanic area is strike-slip faulting, the orientation of the principal compressive stress axis is NE-SW, the orientation of the principal extension stress axis is SE-NW, the principal compressive and extension stress axes are nearly horizontal, and the dip angle of intermediate principal stress axis is relatively large. This reflects that the volcanic and seismic activities in the Tengchong volcanic area are mainly controlled by the collision and squeezing effect of the Indian-Eurasian plate. It also reflects that the current tensile action caused by deep magma activity has little influence on the shallow crustal stress field. Second, the stress field along fault zones reveals that there exist local stress fields, such as the thrust stress regime at the strike-slip fault terminal area, which is consistent with the compressional area at the intersection of conjugate strike-slip faults indicated by previous study. Third, the stress field results are consistent, regardless of using the original location in the bulletin or the relocated location, indicating that the influence of the event location error can be neglected when there are sufficient data and reflecting the stability of the composite focal mechanism method. The findings can serve as a reference for investigating geological structure movement, seismic activities, and volcanic activities in the Tengchong volcanic area. [ABSTRACT FROM AUTHOR]

Abstract: This paper analyzes the spatial evolution character of multi-objective evolutionary algorithms using self-organized criticality theory. The spatial evolution character is modeled by the statistical property of crowding distance, which displays a scale-free feature and a power-law distribution. We propose that the evolutional rule of multi-objective optimization algorithms is a self-organized state transition from an initial scale-free state to a final scale-free state. The target is to get close to a critical state representing the true Pareto-optimal front. Besides, the anti-Matthew effect is the internal incentive factor of most strategies. The final scale-free state reflects the quality of the final Pareto-optimal front. The speed of the state transition reflects the efficiency of the algorithm. We simulate the spatial evolution characters of three typical multi-objective evolutionary algorithms representing three fields, i.e., Genetic Algorithm, Differential Evolution and the Artificial Immune System algorithm. The results prove that the model and the explanation are effective for analyzing the evolutional rule of multi-objective evolutionary algorithms. [Copyright &y& Elsevier]