Computing upper bounds of the positive real roots of some polynomials is a key step of those real root isolation algorithms based on continued fraction expansion and Vincent's theorem.The authors give a new algori...Computing upper bounds of the positive real roots of some polynomials is a key step of those real root isolation algorithms based on continued fraction expansion and Vincent's theorem.The authors give a new algorithm for computing an upper bound of positive roots in this paper.The complexity of the algorithm is O(n log(uH-l))additions and multiplications where u is the optimal upper bound satisfying Theorem 3.1 of this paper and n is the degree of the polynomial.The method together w辻h some tricks have been implemented as a software package logcf using C language.Experiments on many benchmarks show that logcf is competitive with Root Intervals of Mathematica and the function realroot of Maple averagely and it is much faster than existing open source real root solvers in many test cases.展开更多
To solve nonlinear system of equation,F(x) = 0,a continuous Newton flow x_t(t) = V(x) =-(DF(x))^(-1)F(x),x(0) =x^0 and its mathematical properties,such as the central field,global existence and uniqueness of real root...To solve nonlinear system of equation,F(x) = 0,a continuous Newton flow x_t(t) = V(x) =-(DF(x))^(-1)F(x),x(0) =x^0 and its mathematical properties,such as the central field,global existence and uniqueness of real roots and the structure of the singular surface,are studied.We concisely introduce random Newton flow algorithm(NFA) for finding all roots,based on discrete Newton flow x^(j+1)=x^j+hV{x^j) with random initial value x^0 and h∈(0,1],and three computable quantities,g_j,d_j and K_j.The numerical experiments with dimension n=300 are provided.展开更多
In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate t...In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate the flexibility and effectiveness of the algorithm.展开更多
The root multiple signal classification（root-MUSIC） algorithm is one of the most important techniques for direction of arrival（DOA） estimation. Using a uniform linear array（ULA） composed of M sensors, this metho...The root multiple signal classification（root-MUSIC） algorithm is one of the most important techniques for direction of arrival（DOA） estimation. Using a uniform linear array（ULA） composed of M sensors, this method usually estimates L signal DOAs by finding roots that lie closest to the unit circle of a（2M-1）-order polynomial, where L 〈 M. A novel efficient root-MUSIC-based method for direction estimation is presented, in which the order of polynomial is efficiently reduced to 2L. Compared with the unitary root-MUSIC（U-root-MUSIC） approach which involves real-valued computations only in the subspace decomposition stage, both tasks of subspace decomposition and polynomial rooting are implemented with real-valued computations in the new technique,which hence shows a significant efficiency advantage over most state-of-the-art techniques. Numerical simulations are conducted to verify the correctness and efficiency of the new estimator.展开更多
It is well-recognized that a transfer system response delay that reduces the test stability inevitably exists in real-time dynamic hybrid testing （RTDHT）. This paper focuses on the delay-dependent stability and adde...It is well-recognized that a transfer system response delay that reduces the test stability inevitably exists in real-time dynamic hybrid testing （RTDHT）. This paper focuses on the delay-dependent stability and added damping of SDOF systems in RTDHT. The exponential delay term is transferred into a rational fraction by the Pad6 approximation, and the delay-dependent stability conditions and instability mechanism of SDOF RTDHT systems are investigated by the root locus technique. First, the stability conditions are discussed separately for the cases of stiffness, mass, and damping experimental substructure. The use of root locus plots shows that the added damping effect and instability mechanism for mass are different from those for stiffness. For the stiffness experimental substructure case, the instability results from the inherent mode because of an obvious negative damping effect of the delay. For the mass case, the delay introduces an equivalent positive damping into the inherent mode, and instability occurs at an added high frequency mode. Then, the compound stability condition is investigated for a general case and the results show that the mass ratio may have both upper and lower limits to remain stable. Finally, a high-emulational virtual shaking table model is built to validate the stability conclusions.展开更多
In this note, for any pair of natural numbers (n,k), n≥3, k≥1, and 2k<n, we construct an infinite family of irreducible polynomials of degree n, with integer coefficients, that has exactly ...In this note, for any pair of natural numbers (n,k), n≥3, k≥1, and 2k<n, we construct an infinite family of irreducible polynomials of degree n, with integer coefficients, that has exactly n-2k?complex non-real roots if n is even and has exactly n-2k-1?complex non-real roots if n is odd. Our work generalizes a technical result of R. Bauer, presented in the classical monograph “Basic Algebra” of N. Jacobson. It is used there to construct polynomials with Galois groups, the symmetric group. Bauer’s result covers the case k=1?and n odd prime.展开更多
In this paper we propose two original iterated maps to numerically approximate the nth root of a real number. Comparisons between the new maps and the famous Newton-Raphson method are carried out, including fixed poin...In this paper we propose two original iterated maps to numerically approximate the nth root of a real number. Comparisons between the new maps and the famous Newton-Raphson method are carried out, including fixed point determination, stability analysis and measure of the mean convergence time, which is confirmed by our analytical convergence time model. Stability of solutions is confirmed by measuring the Lyapunov exponent over the parameter space of each map. A generalization of the second map is proposed, giving rise to a family of new maps to address the same problem. This work is developed within the language of discrete dynamical systems.展开更多
In the existing Statistics and Econometrics literature, there does not exist a statistical test which may test for all kinds of roots of the characteristic polynomial leading to an unstable dynamic response, i.e., pos...In the existing Statistics and Econometrics literature, there does not exist a statistical test which may test for all kinds of roots of the characteristic polynomial leading to an unstable dynamic response, i.e., positive and negative real unit roots, complex unit roots and the roots lying inside the unit circle. This paper develops a test which is sufficient to prove dynamic stability (in the context of roots of the characteristic polynomial) of a univariate as well as a multivariate time series without having a structural break. It covers all roots (positive and negative real unit roots, complex unit roots and the roots inside the unit circle whether single or multiple) which may lead to an unstable dynamic response. Furthermore, it also indicates the number of roots causing instability in the time series. The test is much simpler in its application as compared to the existing tests as the series is strictly stationary under the null (C01, C12).展开更多
基金supported by the National Science Foundation of China under Grant Nos.61802318,61732001and 61532019
文摘Computing upper bounds of the positive real roots of some polynomials is a key step of those real root isolation algorithms based on continued fraction expansion and Vincent's theorem.The authors give a new algorithm for computing an upper bound of positive roots in this paper.The complexity of the algorithm is O(n log(uH-l))additions and multiplications where u is the optimal upper bound satisfying Theorem 3.1 of this paper and n is the degree of the polynomial.The method together w辻h some tricks have been implemented as a software package logcf using C language.Experiments on many benchmarks show that logcf is competitive with Root Intervals of Mathematica and the function realroot of Maple averagely and it is much faster than existing open source real root solvers in many test cases.
基金National Natural Science Foundation of China(Grant Nos. 11301176,11071067 and 11226332)
文摘To solve nonlinear system of equation,F(x) = 0,a continuous Newton flow x_t(t) = V(x) =-(DF(x))^(-1)F(x),x(0) =x^0 and its mathematical properties,such as the central field,global existence and uniqueness of real roots and the structure of the singular surface,are studied.We concisely introduce random Newton flow algorithm(NFA) for finding all roots,based on discrete Newton flow x^(j+1)=x^j+hV{x^j) with random initial value x^0 and h∈(0,1],and three computable quantities,g_j,d_j and K_j.The numerical experiments with dimension n=300 are provided.
基金supported by the National Natural Science Foundation of China (Project Nos.60373093 and 60533060)
文摘In this paper, we propose an algorithm for isolating real roots of a given univariate spline function, which is based on the use of Descartes＇ rule of signs and de Casteljau algorithm. Numerical examples illustrate the flexibility and effectiveness of the algorithm.
基金supported by the National Natural Science Foundation of China(61501142)the Shandong Provincial Natural Science Foundation(ZR2014FQ003)+1 种基金the Special Foundation of China Postdoctoral Science(2016T90289)the China Postdoctoral Science Foundation(2015M571414)
文摘The root multiple signal classification（root-MUSIC） algorithm is one of the most important techniques for direction of arrival（DOA） estimation. Using a uniform linear array（ULA） composed of M sensors, this method usually estimates L signal DOAs by finding roots that lie closest to the unit circle of a（2M-1）-order polynomial, where L 〈 M. A novel efficient root-MUSIC-based method for direction estimation is presented, in which the order of polynomial is efficiently reduced to 2L. Compared with the unitary root-MUSIC（U-root-MUSIC） approach which involves real-valued computations only in the subspace decomposition stage, both tasks of subspace decomposition and polynomial rooting are implemented with real-valued computations in the new technique,which hence shows a significant efficiency advantage over most state-of-the-art techniques. Numerical simulations are conducted to verify the correctness and efficiency of the new estimator.
基金State Key Laboratory of Hydroscience and Engineering Under Grant No.2008-TC-2National Natural Science Foundation of China Under Grant No.90510018,50779021 and 90715041
文摘It is well-recognized that a transfer system response delay that reduces the test stability inevitably exists in real-time dynamic hybrid testing （RTDHT）. This paper focuses on the delay-dependent stability and added damping of SDOF systems in RTDHT. The exponential delay term is transferred into a rational fraction by the Pad6 approximation, and the delay-dependent stability conditions and instability mechanism of SDOF RTDHT systems are investigated by the root locus technique. First, the stability conditions are discussed separately for the cases of stiffness, mass, and damping experimental substructure. The use of root locus plots shows that the added damping effect and instability mechanism for mass are different from those for stiffness. For the stiffness experimental substructure case, the instability results from the inherent mode because of an obvious negative damping effect of the delay. For the mass case, the delay introduces an equivalent positive damping into the inherent mode, and instability occurs at an added high frequency mode. Then, the compound stability condition is investigated for a general case and the results show that the mass ratio may have both upper and lower limits to remain stable. Finally, a high-emulational virtual shaking table model is built to validate the stability conclusions.
文摘In this note, for any pair of natural numbers (n,k), n≥3, k≥1, and 2k<n, we construct an infinite family of irreducible polynomials of degree n, with integer coefficients, that has exactly n-2k?complex non-real roots if n is even and has exactly n-2k-1?complex non-real roots if n is odd. Our work generalizes a technical result of R. Bauer, presented in the classical monograph “Basic Algebra” of N. Jacobson. It is used there to construct polynomials with Galois groups, the symmetric group. Bauer’s result covers the case k=1?and n odd prime.
文摘In this paper we propose two original iterated maps to numerically approximate the nth root of a real number. Comparisons between the new maps and the famous Newton-Raphson method are carried out, including fixed point determination, stability analysis and measure of the mean convergence time, which is confirmed by our analytical convergence time model. Stability of solutions is confirmed by measuring the Lyapunov exponent over the parameter space of each map. A generalization of the second map is proposed, giving rise to a family of new maps to address the same problem. This work is developed within the language of discrete dynamical systems.
文摘In the existing Statistics and Econometrics literature, there does not exist a statistical test which may test for all kinds of roots of the characteristic polynomial leading to an unstable dynamic response, i.e., positive and negative real unit roots, complex unit roots and the roots lying inside the unit circle. This paper develops a test which is sufficient to prove dynamic stability (in the context of roots of the characteristic polynomial) of a univariate as well as a multivariate time series without having a structural break. It covers all roots (positive and negative real unit roots, complex unit roots and the roots inside the unit circle whether single or multiple) which may lead to an unstable dynamic response. Furthermore, it also indicates the number of roots causing instability in the time series. The test is much simpler in its application as compared to the existing tests as the series is strictly stationary under the null (C01, C12).
