Computations with polynomials are at the heart of any computer algebra system and also have many applications in engineering, coding theory, and cryptography. Generally speaking, the low-level polynomial computations of interest can be classified as arithmetic operations, algebraic computations, and inverse symbolic problems. New algorithms are presented in all these areas which improve on the state of the art in both theoretical and practical performance. Traditionally, polynomials may be represented in a computer in one of two ways: as a "dense" array of all possible coefficients up to the polynomial's degree, or as a "sparse" list of coefficient-exponent tuples. In the latter case, zero terms are not explicitly written, giving a potentially more compact representation. In the area of arithmetic operations, new algorithms are presented for the multiplication of dense polynomials. These have the same asymptotic time cost of the fastest existing approaches, but reduce the intermediate storage required from linear in the size of the input to a constant amount. Two different algorithms for so-called "adaptive" multiplication are also presented which effectively provide a gradient between existing sparse and dense algorithms, giving a large improvement in many cases while never performing significantly worse than the best existing approaches. Algebraic computations on sparse polynomials are considered as well. The first known polynomial-time algorithm to detect when a sparse polynomial is a perfect power is presented, along with two different approaches to computing the perfect power factorization. Inverse symbolic problems are those for which the challenge is to compute a symbolic mathematical representation of a program or "black box". First, new algorithms are presented which improve the complexity of interpolation for sparse polynomials with coefficients in finite fields or approximate complex numbers. Second, the first polynomial-time algorithm for the more general problem of sparsest-shift interpolation is presented. The practical performance of all these algorithms is demonstrated with implementations in a high-performance library and compared to existing software and previous techniques.

In this thesis, we make some contributions at the interface between algebra and graph theory. In Chapter 1, we give an overview of the topics and also the definitions and preliminaries. In Chapter 2, we estimate the number of possible types degree patterns of k-lacunary polynomials of degree t < p which split completely modulo p. The result is based on a rather unusual combination of two techniques: a bound on the number of zeros of lacunary polynomials and a bound on the so-called domination number of a graph. In Chapter 3, we deal with the determinant of bipartite graphs. The nullity of a graph G is the multiplicity of 0 in the spectrum of G. Nullity of a (molecular) graph (e.g., a bipartite graph corresponding to an alternant hydrocarbon) has important applications in quantum chemistry and Huckel molecular orbital (HMO) theory. A famous problem, posed by Collatz and Sinogowitz in 1957, asks to characterize all graphs with positive nullity. Clearly, examining the determinant of a graph is a way to attack this problem. In this Chapter, we show that the determinant of a bipartite graph with at least two perfect matchings and with all cycle lengths divisible by four, is zero. In Chapter 4, we first introduce an application of spectral graph theory in proving trigonometric identities. This is a very simple double counting argument that gives very short proofs for some of these identities (and perhaps the only existed proof in some cases!). In the rest of Chapter 4, using some properties of the well-known Chebyshev polynomials, we prove some theorems that allow us to evaluate the number of spanning trees in join of graphs, Cartesian product of graphs, and nearly regular graphs. In the last section of Chapter 4, we obtain the number of spanning trees in an (r,s)-semiregular graph and its line graph. Note that the same results, as in the last section, were proved by I. Sato using zeta functions. But our proofs are much shorter based on some well-known facts from spectral graph theory. Besides, we do not use zeta functions in our arguments. In Chapter 5, we present the conclusion and also some possible projects.

Diss. (sammanfattning) Uppsala : Univ., 2004. / Härtill 8 uppsatser.

Thesis (Ph. D.)--Brandeis University, 2008. / "UMI:3306459." MICROFILM COPY ALSO AVAILABLE IN THE UNIVERSITY ARCHIVES. Includes bibliographical references.

Thesis (M.S.); Submitted to Iowa State Univ., Ames, IA (US); 19 Dec 2004. / Published through the Information Bridge: DOE Scientific and Technical Information. "IS-T 2196" Rahul Ravindrudu. US Department of Energy 12/19/2004. Report is also available in paper and microfiche from NTIS.

Thesis (M.S.)--West Virginia University, 1998. / Title from document title page. "Fall 1998." Document formatted into pages; contains iii, 28 p. : ill. (some col.). Includes abstract. Includes bibliographical references (p. 27-28).

Thesis (Ph. D.)--West Virginia University, 1998. / Title from document title page. Document formatted into pages; contains xi, 116 p. : ill. (some col.) Includes abstract. Includes bibliographical references (p. 94-98).

Thesis (Master of Engineering in Ocean Engineering)--University of California at Berkeley, 2004. / "January 2005." Description based on title screen as viewed on May 25, 2010. DTIC Descriptor(s): Fluid Dynamics, Lagrangian Functions, Equations Of Motion, Acceleration, Formulations, Grids, Continuum Mechanics, Gaussian Quadrature, Derivatives (Mathematics), Compact Disks, Boundary Value Problems, Polynomials, Interpolation, Pressure, Operators (Mathematics). DTIC Identifier(s): Multimedia (CD-Rom), Moving Grids, Meshless Discretization, Lifs (Lagrange Implicit Fraction Step), Lagrangian Dynamics, Meshless Operators, Mlip (Multidimensional Lagrange Interpolating Polynomials), Flux Boundary Conditions, Radial Basis Functions Includes bibliographical references (58-59).

Thesis (Ph. D. in Mathematics)--Vanderbilt University, Aug. 2006. / Title from title screen. Includes bibliographical references.

Thesis (MSc (Mathematics))--University of Stellenbosch, 2008. / Subdivision techniques have, over the last two decades, developed into a powerful tool in computer-aided geometric design (CAGD). In some applications it is required that data be preserved exactly; hence the need for interpolatory subdivision schemes. In this thesis,we consider the fundamentals of themathematical analysis of symmetric interpolatory subdivision schemes for curves, also with the property of polynomial filling up to a given odd degree, in the sense that, if the initial control point sequence is situated on such a polynomial curve, all the subsequent subdivision iterates fills up this curve, for it to eventually also become also the limit curve. A subdivision scheme is determined by its mask coefficients, which we find convenient to mathematically describe as a bi-infinite sequnce a with finite support. This sequence is in one-to-one correspondence with a corresponding Laurent polynomial A with coefficients given by the mask sequence a. After an introductory Chapter 1 on notation, basic definitions, and an overview of the thesis, we proceed in Chapter 2 to separately consider the issues of interpolation, symmetry and polynomial filling with respect to a subdivision scheme, eventually leading to a definition of the class Am,n of mask symbols in which all of the above desired properties are combined. We proceed in Chapter 3 to deduce an explicit characterization formula for the classAm,n, in the process also showing that its optimally local member is the well-known Dubuc–Deslauriers (DD) mask symbol Dm of order m. In fact, an alternative explicit characterization result appears in recent work by De Villiers and Hunter, in which the authors characterized mask symbols A ∈Am,n as arbitrary convex combinations of DD mask symbols. It turns out that Am,m = {Dm}, whereas the class Am,m+1 has one degree of freedom, which we interpret here in the formof a shape parameter t ∈ R for the resulting subdivision scheme. In order to investigate the convergence of subdivision schemes associated with mask symbols in Am,n, we first introduce in Chapter 4 the concept of a refinement pair (a,φ), consisting of a finitely-supported sequence a and a finitelysupported function φ, where φ is a refinable function in the sense that it can be expressed as a finite linear combination, as determined by a, of the integer shifts of its own dilation by factor 2. After presenting proofs of a variety of properties satisfied by a given refinement pair (a,φ), we next introduce the concept of an interpolatory refinement pair as one for which the refinable function φ interpolates the delta sequence at the integers. A fundamental result is then that the existence of an interpolatory refinement pair (a,φ) guarantees the convergence of the interpolatory subdivision scheme with subdivision mask a, with limit function © expressible as a linear combination of the integer shifts of φ, and with all the subdivision iterates lying on ©. In Chapter 5, we first present a fundamental result byMicchelli, according to which interpolatory refinable function existence is obtained for mask symbols in Am,n if the mask symbol A is strictly positive on the unit circle in complex plane. After showing that the DD mask symbol Dm satisfies this sufficient property, we proceed to compute the precise t -interval for such positivity on the unit circle to occur for the mask symbols A = Am(t |·) ∈Am,m+1. Also, we compare our numerical results with analogous ones in the literature. Finally, in Chapter 6, we investigate the regularity of refinable functions φ = φm(t |·) corresponding to mask symbols Am(t |·). Using a standard result fromthe literature in which a lower bound on the Hölder continuity exponent of a refinable function φ is given explicitly in terms of the spectral radius of a matrix obtained from the corresponding mask sequence a, we compute this lower bound for selected values of m.