aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/pdecomp.spad.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/pdecomp.spad.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/algebra/pdecomp.spad.pamphlet')
-rw-r--r--src/algebra/pdecomp.spad.pamphlet135
1 files changed, 135 insertions, 0 deletions
diff --git a/src/algebra/pdecomp.spad.pamphlet b/src/algebra/pdecomp.spad.pamphlet
new file mode 100644
index 00000000..37057fc4
--- /dev/null
+++ b/src/algebra/pdecomp.spad.pamphlet
@@ -0,0 +1,135 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra pdecomp.spad}
+\author{The Axiom Team}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package PCOMP PolynomialComposition}
+<<package PCOMP PolynomialComposition>>=
+)abbrev package PCOMP PolynomialComposition
+++ Description:
+++ This package \undocumented
+PolynomialComposition(UP: UnivariatePolynomialCategory(R), R: Ring): with
+ compose: (UP, UP) -> UP
+ ++ compose(p,q) \undocumented
+ == add
+ compose(g, h) ==
+ r: UP := 0
+ while g ^= 0 repeat
+ r := leadingCoefficient(g)*h**degree(g) + r
+ g := reductum g
+ r
+
+@
+\section{package PDECOMP PolynomialDecomposition}
+<<package PDECOMP PolynomialDecomposition>>=
+)abbrev package PDECOMP PolynomialDecomposition
+++ Description:
+++ This package \undocumented
+-- Ref: Kozen and Landau, Cornell University TR 86-773
+PolynomialDecomposition(UP, F): PDcat == PDdef where
+ F:Field
+ UP:UnivariatePolynomialCategory F
+ NNI ==> NonNegativeInteger
+ LR ==> Record(left: UP, right: UP)
+
+ PDcat == with
+ decompose: UP -> List UP
+ ++ decompose(up) \undocumented
+ decompose: (UP, NNI, NNI) -> Union(LR, "failed")
+ ++ decompose(up,m,n) \undocumented
+ leftFactor: (UP, UP) -> Union(UP, "failed")
+ ++ leftFactor(p,q) \undocumented
+ rightFactorCandidate: (UP, NNI) -> UP
+ ++ rightFactorCandidate(p,n) \undocumented
+ PDdef == add
+ leftFactor(f, h) ==
+ g: UP := 0
+ for i in 0.. while f ^= 0 repeat
+ fr := divide(f, h)
+ f := fr.quotient; r := fr.remainder
+ degree r > 0 => return "failed"
+ g := g + r * monomial(1, i)
+ g
+
+ decompose(f, dg, dh) ==
+ df := degree f
+ dg*dh ^= df => "failed"
+ h := rightFactorCandidate(f, dh)
+ g := leftFactor(f, h)
+ g case "failed" => "failed"
+ [g::UP, h]
+
+ decompose f ==
+ df := degree f
+ for dh in 2..df-1 | df rem dh = 0 repeat
+ h := rightFactorCandidate(f, dh)
+ g := leftFactor(f, h)
+ g case UP => return
+ append(decompose(g::UP), decompose h)
+ [f]
+ rightFactorCandidate(f, dh) ==
+ f := f/leadingCoefficient f
+ df := degree f
+ dg := df quo dh
+ h := monomial(1, dh)
+ for k in 1..dh repeat
+ hdg:= h**dg
+ c := (coefficient(f,(df-k)::NNI)-coefficient(hdg,(df-k)::NNI))/(dg::F)
+ h := h + monomial(c, (dh-k)::NNI)
+ h - monomial(coefficient(h, 0), 0) -- drop constant term
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+-- - Redistributions of source code must retain the above copyright
+-- notice, this list of conditions and the following disclaimer.
+--
+-- - Redistributions in binary form must reproduce the above copyright
+-- notice, this list of conditions and the following disclaimer in
+-- the documentation and/or other materials provided with the
+-- distribution.
+--
+-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+-- names of its contributors may be used to endorse or promote products
+-- derived from this software without specific prior written permission.
+--
+--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+@
+<<*>>=
+<<license>>
+
+--% Polynomial composition and decomposition functions
+-- If f = g o h then g = leftFactor(f, h) & h = rightFactor(f, g)
+-- SMW Dec 86
+
+<<package PCOMP PolynomialComposition>>
+<<package PDECOMP PolynomialDecomposition>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}