diff options
Diffstat (limited to 'src/algebra/algcat.spad.pamphlet')
| -rw-r--r-- | src/algebra/algcat.spad.pamphlet | 382 |
1 files changed, 382 insertions, 0 deletions
diff --git a/src/algebra/algcat.spad.pamphlet b/src/algebra/algcat.spad.pamphlet new file mode 100644 index 00000000..5c028319 --- /dev/null +++ b/src/algebra/algcat.spad.pamphlet @@ -0,0 +1,382 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra algcat.spad} +\author{Barry Trager, Claude Quitte, Manuel Bronstein} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{category FINRALG FiniteRankAlgebra} +<<category FINRALG FiniteRankAlgebra>>= +)abbrev category FINRALG FiniteRankAlgebra +++ Author: Barry Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A FiniteRankAlgebra is an algebra over a commutative ring R which +++ is a free R-module of finite rank. + +FiniteRankAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): + Category == Algebra R with + rank : () -> PositiveInteger + ++ rank() returns the rank of the algebra. + regularRepresentation : (% , Vector %) -> Matrix R + ++ regularRepresentation(a,basis) returns the matrix of the + ++ linear map defined by left multiplication by \spad{a} with respect + ++ to the basis \spad{basis}. + trace : % -> R + ++ trace(a) returns the trace of the regular representation + ++ of \spad{a} with respect to any basis. + norm : % -> R + ++ norm(a) returns the determinant of the regular representation + ++ of \spad{a} with respect to any basis. + coordinates : (%, Vector %) -> Vector R + ++ coordinates(a,basis) returns the coordinates of \spad{a} with + ++ respect to the basis \spad{basis}. + coordinates : (Vector %, Vector %) -> Matrix R + ++ coordinates([v1,...,vm], basis) returns the coordinates of the + ++ vi's with to the basis \spad{basis}. The coordinates of vi are + ++ contained in the ith row of the matrix returned by this + ++ function. + represents : (Vector R, Vector %) -> % + ++ represents([a1,..,an],[v1,..,vn]) returns \spad{a1*v1 + ... + an*vn}. + discriminant : Vector % -> R + ++ discriminant([v1,..,vn]) returns + ++ \spad{determinant(traceMatrix([v1,..,vn]))}. + traceMatrix : Vector % -> Matrix R + ++ traceMatrix([v1,..,vn]) is the n-by-n matrix ( Tr(vi * vj) ) + characteristicPolynomial: % -> UP + ++ characteristicPolynomial(a) returns the characteristic + ++ polynomial of the regular representation of \spad{a} with respect + ++ to any basis. + if R has Field then minimalPolynomial : % -> UP + ++ minimalPolynomial(a) returns the minimal polynomial of \spad{a}. + if R has CharacteristicZero then CharacteristicZero + if R has CharacteristicNonZero then CharacteristicNonZero + + add + + discriminant v == determinant traceMatrix v + + coordinates(v:Vector %, b:Vector %) == + m := new(#v, #b, 0)$Matrix(R) + for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat + setRow_!(m, j, coordinates(qelt(v, i), b)) + m + + represents(v, b) == + m := minIndex v - 1 + _+/[v(i+m) * b(i+m) for i in 1..rank()] + + traceMatrix v == + matrix [[trace(v.i*v.j) for j in minIndex v..maxIndex v]$List(R) + for i in minIndex v .. maxIndex v]$List(List R) + + regularRepresentation(x, b) == + m := minIndex b - 1 + matrix + [parts coordinates(x*b(i+m),b) for i in 1..rank()]$List(List R) + +@ +\section{category FRAMALG FramedAlgebra} +<<category FRAMALG FramedAlgebra>>= +)abbrev category FRAMALG FramedAlgebra +++ Author: Barry Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A \spadtype{FramedAlgebra} is a \spadtype{FiniteRankAlgebra} together +++ with a fixed R-module basis. + +FramedAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): + Category == FiniteRankAlgebra(R, UP) with + --operations + basis : () -> Vector % + ++ basis() returns the fixed R-module basis. + coordinates : % -> Vector R + ++ coordinates(a) returns the coordinates of \spad{a} with respect to the + ++ fixed R-module basis. + coordinates : Vector % -> Matrix R + ++ coordinates([v1,...,vm]) returns the coordinates of the + ++ vi's with to the fixed basis. The coordinates of vi are + ++ contained in the ith row of the matrix returned by this + ++ function. + represents : Vector R -> % + ++ represents([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where + ++ v1, ..., vn are the elements of the fixed basis. + convert : % -> Vector R + ++ convert(a) returns the coordinates of \spad{a} with respect to the + ++ fixed R-module basis. + convert : Vector R -> % + ++ convert([a1,..,an]) returns \spad{a1*v1 + ... + an*vn}, where + ++ v1, ..., vn are the elements of the fixed basis. + traceMatrix : () -> Matrix R + ++ traceMatrix() is the n-by-n matrix ( \spad{Tr(vi * vj)} ), where + ++ v1, ..., vn are the elements of the fixed basis. + discriminant : () -> R + ++ discriminant() = determinant(traceMatrix()). + regularRepresentation : % -> Matrix R + ++ regularRepresentation(a) returns the matrix of the linear + ++ map defined by left multiplication by \spad{a} with respect + ++ to the fixed basis. + --attributes + --separable <=> discriminant() ^= 0 + add + convert(x:%):Vector(R) == coordinates(x) + convert(v:Vector R):% == represents(v) + traceMatrix() == traceMatrix basis() + discriminant() == discriminant basis() + regularRepresentation x == regularRepresentation(x, basis()) + coordinates x == coordinates(x, basis()) + represents x == represents(x, basis()) + + coordinates(v:Vector %) == + m := new(#v, rank(), 0)$Matrix(R) + for i in minIndex v .. maxIndex v for j in minRowIndex m .. repeat + setRow_!(m, j, coordinates qelt(v, i)) + m + + regularRepresentation x == + m := new(n := rank(), n, 0)$Matrix(R) + b := basis() + for i in minIndex b .. maxIndex b for j in minRowIndex m .. repeat + setRow_!(m, j, coordinates(x * qelt(b, i))) + m + + characteristicPolynomial x == + mat00 := (regularRepresentation x) + mat0 := map(#1 :: UP,mat00)$MatrixCategoryFunctions2(R, Vector R, + Vector R, Matrix R, UP, Vector UP,Vector UP, Matrix UP) + mat1 : Matrix UP := scalarMatrix(rank(),monomial(1,1)$UP) + determinant(mat1 - mat0) + + if R has Field then + -- depends on the ordering of results from nullSpace, also see FFP + minimalPolynomial(x:%):UP == + y:%:=1 + n:=rank() + m:Matrix R:=zero(n,n+1) + for i in 1..n+1 repeat + setColumn_!(m,i,coordinates(y)) + y:=y*x + v:=first nullSpace(m) + +/[monomial(v.(i+1),i) for i in 0..#v-1] + +@ +\section{category MONOGEN MonogenicAlgebra} +<<category MONOGEN MonogenicAlgebra>>= +)abbrev category MONOGEN MonogenicAlgebra +++ Author: Barry Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ A \spadtype{MonogenicAlgebra} is an algebra of finite rank which +++ can be generated by a single element. + +MonogenicAlgebra(R:CommutativeRing, UP:UnivariatePolynomialCategory R): + Category == + Join(FramedAlgebra(R, UP), CommutativeRing, ConvertibleTo UP, + FullyRetractableTo R, FullyLinearlyExplicitRingOver R) with + generator : () -> % + ++ generator() returns the generator for this domain. + definingPolynomial: () -> UP + ++ definingPolynomial() returns the minimal polynomial which + ++ \spad{generator()} satisfies. + reduce : UP -> % + ++ reduce(up) converts the univariate polynomial up to an algebra + ++ element, reducing by the \spad{definingPolynomial()} if necessary. + convert : UP -> % + ++ convert(up) converts the univariate polynomial up to an algebra + ++ element, reducing by the \spad{definingPolynomial()} if necessary. + lift : % -> UP + ++ lift(z) returns a minimal degree univariate polynomial up such that + ++ \spad{z=reduce up}. + if R has Finite then Finite + if R has Field then + Field + DifferentialExtension R + reduce : Fraction UP -> Union(%, "failed") + ++ reduce(frac) converts the fraction frac to an algebra element. + derivationCoordinates: (Vector %, R -> R) -> Matrix R + ++ derivationCoordinates(b, ') returns M such that \spad{b' = M b}. + if R has FiniteFieldCategory then FiniteFieldCategory + add + convert(x:%):UP == lift x + convert(p:UP):% == reduce p + generator() == reduce monomial(1, 1)$UP + norm x == resultant(definingPolynomial(), lift x) + retract(x:%):R == retract lift x + retractIfCan(x:%):Union(R, "failed") == retractIfCan lift x + + basis() == + [reduce monomial(1,i)$UP for i in 0..(rank()-1)::NonNegativeInteger] + + characteristicPolynomial(x:%):UP == + characteristicPolynomial(x)$CharacteristicPolynomialInMonogenicalAlgebra(R,UP,%) + + if R has Finite then + size() == size()$R ** rank() + random() == represents [random()$R for i in 1..rank()]$Vector(R) + + if R has Field then + reduce(x:Fraction UP) == reduce(numer x) exquo reduce(denom x) + + differentiate(x:%, d:R -> R) == + p := definingPolynomial() + yprime := - reduce(map(d, p)) / reduce(differentiate p) + reduce(map(d, lift x)) + yprime * reduce differentiate lift x + + derivationCoordinates(b, d) == + coordinates(map(differentiate(#1, d), b), b) + + recip x == + (bc := extendedEuclidean(lift x, definingPolynomial(), 1)) + case "failed" => "failed" + reduce(bc.coef1) + +@ +\section{package CPIMA CharacteristicPolynomialInMonogenicalAlgebra} +<<package CPIMA CharacteristicPolynomialInMonogenicalAlgebra>>= +)abbrev package CPIMA CharacteristicPolynomialInMonogenicalAlgebra +++ Author: Claude Quitte +++ Date Created: 10/12/93 +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ This package implements characteristicPolynomials for monogenic algebras +++ using resultants +CharacteristicPolynomialInMonogenicalAlgebra(R : CommutativeRing, + PolR : UnivariatePolynomialCategory(R), + E : MonogenicAlgebra(R, PolR)): with + characteristicPolynomial : E -> PolR + ++ characteristicPolynomial(e) returns the characteristic polynomial + ++ of e using resultants + + == add + Pol ==> SparseUnivariatePolynomial + + import UnivariatePolynomialCategoryFunctions2(R, PolR, PolR, Pol(PolR)) + XtoY(Q : PolR) : Pol(PolR) == map(monomial(#1, 0), Q) + + P : Pol(PolR) := XtoY(definingPolynomial()$E) + X : Pol(PolR) := monomial(monomial(1, 1)$PolR, 0) + + characteristicPolynomial(x : E) : PolR == + Qx : PolR := lift(x) + -- on utilise le fait que resultant_Y (P(Y), X - Qx(Y)) + return resultant(P, X - XtoY(Qx)) + +@ +\section{package NORMMA NormInMonogenicAlgebra} +<<package NORMMA NormInMonogenicAlgebra>>= +)abbrev package NORMMA NormInMonogenicAlgebra +++ Author: Manuel Bronstein +++ Date Created: 23 February 1995 +++ Date Last Updated: 23 February 1995 +++ Basic Functions: norm +++ Description: +++ This package implements the norm of a polynomial with coefficients +++ in a monogenic algebra (using resultants) + +NormInMonogenicAlgebra(R, PolR, E, PolE): Exports == Implementation where + R: GcdDomain + PolR: UnivariatePolynomialCategory R + E: MonogenicAlgebra(R, PolR) + PolE: UnivariatePolynomialCategory E + + SUP ==> SparseUnivariatePolynomial + + Exports ==> with + norm: PolE -> PolR + ++ norm q returns the norm of q, + ++ i.e. the product of all the conjugates of q. + + Implementation ==> add + import UnivariatePolynomialCategoryFunctions2(R, PolR, PolR, SUP PolR) + + PolR2SUP: PolR -> SUP PolR + PolR2SUP q == map(#1::PolR, q) + + defpol := PolR2SUP(definingPolynomial()$E) + + norm q == + p:SUP PolR := 0 + while q ~= 0 repeat + p := p + monomial(1,degree q)$PolR * PolR2SUP lift leadingCoefficient q + q := reductum q + primitivePart resultant(p, defpol) + +@ +\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>> + +<<category FINRALG FiniteRankAlgebra>> +<<category FRAMALG FramedAlgebra>> +<<category MONOGEN MonogenicAlgebra>> +<<package CPIMA CharacteristicPolynomialInMonogenicalAlgebra>> +<<package NORMMA NormInMonogenicAlgebra>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |