Factoring polynomials is a central problem in computational algebra and numbertheory and is a basic routine in most computeralgebra systems (e.g. Maple, Mathematica, Magma, etc). It has been extensively studied in t...
Factoring polynomials is a central problem in computational algebra and numbertheory and is a basic routine in most computeralgebra systems (e.g. Maple, Mathematica, Magma, etc). It has been extensively studied in the last few decades by many mathematicians and computer scientists. The main approaches include Berlekamp's method (1967) based on the kernel of Frobenius map, Niederreiter's method (1993) via an ordinary differential equation, Zassenhaus's modular approach (1969), Lenstra, Lenstra and Lovasz's lattice reduction (1982), and Gao's method via a partial differential equation (2003). These methods and their recent improvements due to van Hoeij (2002) and Lecerf et al (2006– 2007) provide efficient algorithms that are widely used in practice today. This thesis studies two issues on polynomial factorization. One is to improve the efficiency of modular approach for factoring bivariate polynomials over finite fields. The usual modular approach first solves a modular linear equation (from Berlekamp's equation or Niederreiter's differential equation), then performs Hensel lifting of modular factors, and finally finds right combinations. An alternative method is presented in this thesis that performs Hensel lifting at the linear algebra stage instead of lifting modular factors. In this way, there is no need to find the right combinations of modular factors, and it finds instead the right linear space from which the irreducible factors can be computed via gcd. The main advantage of this method is that extra solutions can be eliminated at the early stage of computation, so improving on previous Hensel lifting methods. Another issue is about whether random numbers are essential in designing efficient algorithms for factoring polynomials. Although polynomials can be quickly factored by randomized polynomial time algorithms in practice, it is still an open problem whether there exists any deterministic polynomial time algorithm, even if generalized Riemann hypothesis (
Structured methodologies are a popular and powerful tool in information systems development. Many different ones exist, each employing a number of models and so a specification must be converted from one form to anoth...
详细信息
Structured methodologies are a popular and powerful tool in information systems development. Many different ones exist, each employing a number of models and so a specification must be converted from one form to another during the development process. To solve this problem, Dr. Tse proposes a unifying framework behind popular structured models. He approaches the problem from the viewpoints of algebra and category theory. He not only develops the frameworks but also illustrates their practical and theoretical usefulness. Thus, this book will provide insight for software engineers into how methodologies can be formalized, and will open up a range of applications and problems for theoretical computer scientists.
Let A(lambda) be a complex regular matrix polynomial of degree l with g elementary divisors corresponding to the finite eigenvalue;lambda(0). We show that for most complex matrix polynomials B(lambda) with degree at m...
详细信息
Let A(lambda) be a complex regular matrix polynomial of degree l with g elementary divisors corresponding to the finite eigenvalue;lambda(0). We show that for most complex matrix polynomials B(lambda) with degree at most l satisfying rank B(lambda(0)) < g the perturbed polynomial (A + B)(lambda) has exactly g - rank B(lambda(0)) elementary divisors corresponding to lambda(0), and we determine their degrees. If rank B(lambda(0)) + rank(B(lambda) - B(lambda(0)) does not exceed the number of lambda(0)-elementary divisors of A(lambda) with degree greater than 1, then the lambda(0)-elementary divisors of (A + B)(lambda) are the g - rank B(lambda(0)) - rank (B(lambda) - B(lambda(0))) elementary divisors of A(lambda) corresponding to lambda(0) with smallest degree, together with rank(B(lambda) - B(lambda(0))) linear lambda(0)-elementary divisors. Otherwise, the degree of all the ko-elementary divisors of (A + B)(lambda) is one. This behavior happens for any matrix polynomial B(lambda) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most l. If A(lambda) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial. (C) 2008 Elsevier Inc. All right reserved.
The Combinatorial Nullstellensatz can be used to solve certain problems in combinatorics. However, one of the major complications in using the Combinatorial Nullstellensatz is ensuring that there exists a nonzero mono...
The Combinatorial Nullstellensatz can be used to solve certain problems in combinatorics. However, one of the major complications in using the Combinatorial Nullstellensatz is ensuring that there exists a nonzero monomial. This dissertation looks at applying the Combinatorial Nullstellensatz to finding perfect matchings in bipartite graphs. The first two chapters provide background material covering topics such as linear algebra, group theory, graph theory and even the discrete Fourier transform. New results start in the third chapter, showing that the Combinatorial Nullstellensatz can be used to solve the problem of finding perfect matchings in bipartite graphs. Using the Combinatorial Nullstellensatz also allows for a vice use of matroid intersection to find the nonzero monomial. By also applying the uncertainty principle, the number of perfect matchings in a bipartite graph can be bound. The fourth chapter examines properties of the polynomials created in the use of the Combinatorial Nullstellensatz to find perfect matchings in bipartite graphs. Many of the properties of the polynomials have analogous properties for the transforms of the polynomials, which are also examined. These properties often relate back to the structure of the graph which gave rise to the polynomial. The fifth chapter provides an application of the results. Since finding a nonzero monomial can be difficult and the polynomials created in this dissertation give polynomials with such a nonzero monomial the application shows how certain polynomials can be rewritten in terms of the matching polynomials. Such a rewriting may permit an easy method to find a nonzero monomial so that the Combinatorial Nullstellensatz can be applied to the polynomial. Finally, the fifth chapter concludes with some open problems that may be areas of further research.
To develop computational learning theory of commutative regular shuffle closed languages, we study finite elasticity for classes of (semi)group-like structures. One is the. class of AN(d) + F such that A is a matrix o...
详细信息
ISBN:
(纸本)9783642009815
To develop computational learning theory of commutative regular shuffle closed languages, we study finite elasticity for classes of (semi)group-like structures. One is the. class of AN(d) + F such that A is a matrix of size e x d with nonnegative integer entries and F consists of at most k number of e-dimensional nonnegative integer vectors, and another is the class chi(d)(k) of AZ(d) + F such that A is a square matrix of size d with integer entries and F consists of at most k number of dimensional integer vectors (F is repeated according to the lattice AZ(d)). Each class turns out, to be the element-wise unions of k-copies of a more manageable class. So we formulate "learning time" of a class and then study in general setting how much "learning time" is increased by the elementwise union, by using Ramsey number, We also point out, that such a standpoint can be generalized by using Noetherian spaces.
The algebraic framework introduced in [Koutis, Proc. of the 35(th) ICALP 2008] reduces several combinatorial problems in parameterized complexity to the problem of detecting multilinear degree-k monomials hi polynomia...
详细信息
ISBN:
(纸本)9783642029264
The algebraic framework introduced in [Koutis, Proc. of the 35(th) ICALP 2008] reduces several combinatorial problems in parameterized complexity to the problem of detecting multilinear degree-k monomials hi polynomials presented as circuits. The best known (randomized) algorithm for this problem requires only O*(2(k)) time and oracle access to an arithmetic circuit, i.e. the ability to evaluate the circuit on elements from a suitable group algebra. This algorithm has been used to obtain the best;known algorithms for several parameterized problems. In this paper we use communication complexity to show that the O*(2(k)) algorithm is essentially optimal. within this evaluation, oracle framework. On the positive side, we give new applications of the method: finding a copy of a given tree on k nodes, a spanning tree with at least k leaves, a minimum set of nodes that dominate atleast t nodes, and an in-dimensional k-matching. In each case we achieve a faster algorithm than what was known. We also apply the algebraic method to problems in exact counting. Among other results, we show that a combination of dynamic programming and a, variation of the algebraic method can break the trivial upper bounds for exact parameterized counting in fairly general settings.
We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These include the temporal logics CTL and EF, and...
详细信息
ISBN:
(纸本)9780769537467
We use the recently developed theory of forest algebras to find algebraic characterizations of the languages of unranked trees and forests definable in various logics. These include the temporal logics CTL and EF, and first-order logic over the ancestor relation. While the characterizations are in general non-effective, we are able to use them to formulate necessary conditions for definability and provide new proofs that a number of languages are not definable in these logics.
A number of problems in system theory, signal processing, and computeralgebra fit into a generic structured low-rank approximation problem. Several problems of this type are reviewed and efficient local optimization ...
详细信息
The LLL algorithm is a polynomial-time lattice reduction algorithm, named after its inventors, Arjen Lenstra, Hendrik Lenstra and Lszl Lovsz. The algorithm has revolutionized computational aspects of the geometry of n...
ISBN:
(纸本)9783642022944
The LLL algorithm is a polynomial-time lattice reduction algorithm, named after its inventors, Arjen Lenstra, Hendrik Lenstra and Lszl Lovsz. The algorithm has revolutionized computational aspects of the geometry of numbers since its introduction in 1982, leading to breakthroughs in fields as diverse as computeralgebra, cryptology and algorithmic numbertheory. This book consists of 15 survey chapters on computational aspects of Euclidean lattices and their main applications. Topics covered include polynomial factorization, lattice reduction algorithms, applications in numbertheory, integer programming, provable security, lattice-based cryptography and complexity. The authors include many detailed motivations, explanations and examples, and the contributions are largely self-contained. The book will be of value to a wide range of researchers and graduate students working in related fields of theoretical computer science and mathematics.
暂无评论