Motivated by Sasaki＇s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynom...Motivated by Sasaki＇s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is etIicient, especially for sparse bivariate polynomials.展开更多
Factorization of polynomials is one of the foundations of symbolic computation.Its applications arise in numerous branches of mathematics and other sciences.However,the present advanced programming languages such as C...Factorization of polynomials is one of the foundations of symbolic computation.Its applications arise in numerous branches of mathematics and other sciences.However,the present advanced programming languages such as C++ and J++,do not support symbolic computation directly.Hence,it leads to difficulties in applying factorization in engineering fields.In this paper,the authors present an algorithm which use numerical method to obtain exact factors of a bivariate polynomial with rational coefficients.The proposed method can be directly implemented in efficient programming language such C++ together with the GNU Multiple-Precision Library.In addition,the numerical computation part often only requires double precision and is easily parallelizable.展开更多
In this paper, we study the factorization of bi-orthogonal Laurent polynomial wavelet matrices with degree one into simple blocks. A conjecture about advanced factorization is given.
A new necessary and sufficient condition for the existence of minor left prime factorizations of multivariate polynomial matrices without full row rank is presented.The key idea is to establish a relationship between ...A new necessary and sufficient condition for the existence of minor left prime factorizations of multivariate polynomial matrices without full row rank is presented.The key idea is to establish a relationship between a matrix and any of its full row rank submatrices.Based on the new result,the authors propose an algorithm for factorizing matrices and have implemented it on the computer algebra system Maple.Two examples are given to illustrate the effectiveness of the algorithm,and experimental data shows that the algorithm is efficient.展开更多
In this paper it is shown m two different ways that one of the family of parallel iterations to determine all real quadratic factors of polynomials presented in [12] is Newton's method applied to the special equat...In this paper it is shown m two different ways that one of the family of parallel iterations to determine all real quadratic factors of polynomials presented in [12] is Newton's method applied to the special equation (1.7) below. Furthermore, we apply Chebyshev's method to (1.7) and obtain a new parallel iteration for factorization of polynomials. Finally, some properties of the parallel iterations are discussed.展开更多
We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve th...We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.展开更多
基金supported by National Natural Science Foundation of China(GrantNos.91118001 and 11170153)National Key Basic Research Project of China(Grant No.2011CB302400)Chongqing Science and Technology Commission Project(Grant No.cstc2013jjys40001)
文摘Motivated by Sasaki＇s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is etIicient, especially for sparse bivariate polynomials.
基金partly supported by the National Natural Science Foundation of China under Grant Nos.91118001 and 11170153the National Key Basic Research Project of China under Grant No.2011CB302400Chongqing Science and Technology Commission Project under Grant No.cstc2013jjys40001
文摘Factorization of polynomials is one of the foundations of symbolic computation.Its applications arise in numerous branches of mathematics and other sciences.However,the present advanced programming languages such as C++ and J++,do not support symbolic computation directly.Hence,it leads to difficulties in applying factorization in engineering fields.In this paper,the authors present an algorithm which use numerical method to obtain exact factors of a bivariate polynomial with rational coefficients.The proposed method can be directly implemented in efficient programming language such C++ together with the GNU Multiple-Precision Library.In addition,the numerical computation part often only requires double precision and is easily parallelizable.
基金The work was partially supported by NSFC # 69735052
文摘In this paper, we study the factorization of bi-orthogonal Laurent polynomial wavelet matrices with degree one into simple blocks. A conjecture about advanced factorization is given.
基金supported by the National Natural Science Foundation of China under Grant Nos.12171469,12001030 and 12201210the National Key Research and Development Program under Grant No.2020YFA0712300the Fundamental Research Funds for the Central Universities under Grant No.2682022CX048。
文摘A new necessary and sufficient condition for the existence of minor left prime factorizations of multivariate polynomial matrices without full row rank is presented.The key idea is to establish a relationship between a matrix and any of its full row rank submatrices.Based on the new result,the authors propose an algorithm for factorizing matrices and have implemented it on the computer algebra system Maple.Two examples are given to illustrate the effectiveness of the algorithm,and experimental data shows that the algorithm is efficient.
基金The Project Supported by National Natural Science Foundation of China and by Natural Science Foundation of Zhejiang Province.
文摘In this paper it is shown m two different ways that one of the family of parallel iterations to determine all real quadratic factors of polynomials presented in [12] is Newton's method applied to the special equation (1.7) below. Furthermore, we apply Chebyshev's method to (1.7) and obtain a new parallel iteration for factorization of polynomials. Finally, some properties of the parallel iterations are discussed.
文摘We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n 2 + n 1+o(1)logq) to O(n 1.9998 + n 1+o(1)logq) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n × n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii) we decrease from O(m 1.575 n) to O(m 1.5356 n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.
