Search Results

Documents authored by Watt, Stephen M.

Document
DOI: 10.4230/DagSemProc.06271.15
Two Families of Algorithms for Symbolic Polynomials

Authors: Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We wish to work with polynomials where the exponents are not known in advance, such as $x^{2n} - 1$. There are various operations we will want to be able to do, such as squaring the value to get $x^{4n}-2x^{2n}+1$, or differentiating it to get $2nx^{2n-1}$. Expressions of this sort arise frequently in practice, for example in the analysis of algorithms, and it is very difficult to work with them effectively in current computer algebra systems. We consider the case where multivariate polynomials can have exponents which are themselves integer-valued multivariate polynomials, and we present algorithms to compute their GCD and factorization. The algorithms fall into two families: algebraic extension methods and interpolation methods. The first family of algorithms uses the algebraic independence of $x$, $x^n$, $x^{n^2}$, $x^{nm}, etc, to solve related problems with more indeterminates. Some subtlety is needed to avoid problems with fixed divisors of the exponent polynomials. The second family of algorithms uses evaluation and interpolation of the exponent polynomials. While these methods can run into unlucky evaluation points, in many cases they can be more appealing. Additionally, we also treat the case of symbolic exponents on rational coefficients (e.g. $4^{n^2+n}-81$) and show how to avoid integer factorization.
Cite as

Stephen M. Watt. Two Families of Algorithms for Symbolic Polynomials. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.15,
  author =	{Watt, Stephen M.},
  title =	{{Two Families of Algorithms for Symbolic Polynomials}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.15},
  URN =		{urn:nbn:de:0030-drops-7933},
  doi =		{10.4230/DagSemProc.06271.15},
  annote =	{Keywords: Computer algebra, symbolic computation, factorization, gcd, symbolic exponents}
}
Document
DOI: 10.4230/DagSemProc.06271.1
06271 Abstracts Collection – Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
From 02.07.06 to 07.07.06, the Dagstuhl Seminar 06271 ``Challenges in Symbolic Computation Software'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Abstracts Collection – Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.1,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Abstracts Collection – Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.1},
  URN =		{urn:nbn:de:0030-drops-7814},
  doi =		{10.4230/DagSemProc.06271.1},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid, symbolic-numerical methods, algorithm design, symbolic computation languages, systems and user interfaces}
}
Document
DOI: 10.4230/DagSemProc.06271.13
Pivot-Free Block Matrix Inversion

Authors: Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We present a pivot-free deterministic algorithm for the inversion of block matrices. The method is based on the Moore-Penrose inverse and is applicable over certain general classes of rings. This improves on previous methods that required at least one invertible on-diagonal block, and that otherwise required row- or column-based pivoting, disrupting the block structure. Our method is applicable to any invertible matrix and does not require any particular blocks to invertible. This is achieved at the cost of two additional specialized matrix multiplications and, in some cases, requires the inversion to be performed in an extended ring.
Cite as

Stephen M. Watt. Pivot-Free Block Matrix Inversion. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.13,
  author =	{Watt, Stephen M.},
  title =	{{Pivot-Free Block Matrix Inversion}},
  booktitle =	{Challenges in Symbolic Computation Software},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.13},
  URN =		{urn:nbn:de:0030-drops-7806},
  doi =		{10.4230/DagSemProc.06271.13},
  annote =	{Keywords: Linear algebra, block matrices, matrix inverse}
}
Document
DOI: 10.4230/DagSemProc.06271.2
06271 Executive Summary - Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Symbolic computation software allows mathematicians, scientists, engineers, or educators to deal with elaborate calculations using a computer. The applications range from introducing the experimental method in fields of pure mathematics to practical applications, for instance, in cryptology, robotics, or signal theory. The software includes mainstream commercial products such as Maple or Mathematica and highly specialized, public domain systems such as CoCoa, Macaulay2, or Singular. Symbolic computation software implements a variety of sophisticated algorithms on polynomials, matrices, combinatorial structures, and other mathematical objects in a multitude of different dense, sparse, or implicit (black box) representations. The subject of the seminar was innovation in algorithms and software, bringing algorithm designers, software builders, and software users together.
Cite as

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Executive Summary - Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.2,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Executive Summary - Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.2},
  URN =		{urn:nbn:de:0030-drops-7778},
  doi =		{10.4230/DagSemProc.06271.2},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid symbolic-numerical methods, algori}
}
Document
DOI: 10.4230/DagSemProc.06271.8
Coxeter Lattice Paths

Authors: Thomas J. Ashby, Anthony D. Kennedy, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
This talk concerns generating code for running computationally intensive numerical lattice QCD simulations on large parallel computers, using an approach based on the theory of Coxeter groups. Many physical systems have inherent symmetry, and this is usually implicit in the calculations needed to simulate them using discrete approximations, and thus in the associated code. By reversing this and basing the generation of code on the symmetry group of the lattice in question, we arrive at a very natural way of generating and reasoning about programs. The principal aim is a formal way of representing lattices and the paths on these lattices that correspond to the required calculations. This foundation allows the creation and manipulation of lattices and paths to be automated, obviating what can be a labour-intensive and errorprone task. In more detail, a method will be given for representing the points of a regular lattice as elements of the translation subgroup of an affine Coxeter group, by finding the subgroup generators starting from the Coxeter graph of the affine group. Similarly, step sequences are derived as words in the free group generated by the translation subgroup generators themselves. We introduce code generation techniques and the automation of two code optimisations; the grouping of paths into equivalence classes, and the factoring out of common path segments. The latter technique reduces the amount of communication necessary between nodes, and is thus likely to be important in practice.
Cite as

Thomas J. Ashby, Anthony D. Kennedy, and Stephen M. Watt. Coxeter Lattice Paths. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ashby_et_al:DagSemProc.06271.8,
  author =	{Ashby, Thomas J. and Kennedy, Anthony D. and Watt, Stephen M.},
  title =	{{Coxeter Lattice Paths}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.8},
  URN =		{urn:nbn:de:0030-drops-7695},
  doi =		{10.4230/DagSemProc.06271.8},
  annote =	{Keywords: Parallel computing, code generation, Coxeter groups, regular lattices, lattice paths, path optimisation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact