Initial population.

1 files changed, 165 insertions, 0 deletions

diff --git a/src/algebra/lindep.spad.pamphlet b/src/algebra/lindep.spad.pamphlet
new file mode 100644
index 00000000..fb52df5c
--- /dev/null
+++ b/src/algebra/lindep.spad.pamphlet
@@ -0,0 +1,165 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra lindep.spad}
+\author{Manuel Bronstein}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package LINDEP LinearDependence}
+<<package LINDEP LinearDependence>>=
+)abbrev package LINDEP LinearDependence
+++ Test for linear dependence
+++ Author: Manuel Bronstein
+++ Date Created: ???
+++ Date Last Updated: 14 May 1991
+++ Description: Test for linear dependence.
+LinearDependence(S, R): Exports == Implementation where
+  S: IntegralDomain
+  R: LinearlyExplicitRingOver S
+
+  Q ==> Fraction S
+
+  Exports ==> with
+    linearlyDependent?: Vector R -> Boolean
+      ++ \spad{linearlyDependent?([v1,...,vn])} returns true if
+      ++ the vi's are linearly dependent over S, false otherwise.
+    linearDependence  : Vector R -> Union(Vector S, "failed")
+      ++ \spad{linearDependence([v1,...,vn])} returns \spad{[c1,...,cn]} if
+      ++ \spad{c1*v1 + ... + cn*vn = 0} and not all the ci's are 0,
+      ++ "failed" if the vi's are linearly independent over S.
+    if S has Field then
+      solveLinear: (Vector R, R) -> Union(Vector S, "failed")
+        ++ \spad{solveLinear([v1,...,vn], u)} returns \spad{[c1,...,cn]}
+        ++ such that \spad{c1*v1 + ... + cn*vn = u},
+        ++ "failed" if no such ci's exist in S.
+    else
+      solveLinear: (Vector R, R) -> Union(Vector Q, "failed")
+        ++ \spad{solveLinear([v1,...,vn], u)} returns \spad{[c1,...,cn]}
+        ++ such that \spad{c1*v1 + ... + cn*vn = u},
+        ++ "failed" if no such ci's exist in the quotient field of S.
+
+  Implementation ==> add
+    aNonZeroSolution: Matrix S -> Union(Vector S, "failed")
+
+    aNonZeroSolution m ==
+      every?(zero?, v := first nullSpace m) => "failed"
+      v
+
+    linearlyDependent? v ==
+      zero?(n := #v) => true
+--      one? n => zero?(v(minIndex v))
+      (n = 1) => zero?(v(minIndex v))
+      positive? nullity reducedSystem transpose v
+
+    linearDependence v ==
+      zero?(n := #v) => empty()
+--      one? n =>
+      (n = 1) =>
+        zero?(v(minIndex v)) => new(1, 1)
+        "failed"
+      aNonZeroSolution reducedSystem transpose v
+
+    if S has Field then
+      solveLinear(v:Vector R, c:R):Union(Vector S, "failed") ==
+        zero? c => new(#v, 0)
+        empty? v => "failed"
+        sys := reducedSystem(transpose v, new(1, c))
+        particularSolution(sys.mat, sys.vec)$LinearSystemMatrixPackage(S,
+                                           Vector S, Vector S, Matrix S)
+
+    else
+      solveLinear(v:Vector R, c:R):Union(Vector Q, "failed") ==
+        zero? c => new(#v, 0)
+        empty? v => "failed"
+        sys := reducedSystem(transpose v, new(1, c))
+        particularSolution(map(#1::Q, sys.mat)$MatrixCategoryFunctions2(S,
+               Vector S,Vector S,Matrix S,Q,Vector Q,Vector Q,Matrix Q),
+                  map(#1::Q, sys.vec)$VectorFunctions2(S, Q)
+                                    )$LinearSystemMatrixPackage(Q,
+                                           Vector Q, Vector Q, Matrix Q)
+
+@
+\section{package ZLINDEP IntegerLinearDependence}
+<<package ZLINDEP IntegerLinearDependence>>=
+)abbrev package ZLINDEP IntegerLinearDependence
+++ Test for linear dependence over the integers
+++ Author: Manuel Bronstein
+++ Date Created: ???
+++ Date Last Updated: 14 May 1991
+++ Description: Test for linear dependence over the integers.
+IntegerLinearDependence(R): Exports == Implementation where
+  R: LinearlyExplicitRingOver Integer
+
+  Z ==> Integer
+
+  Exports ==> with
+    linearlyDependentOverZ?: Vector R -> Boolean
+      ++ \spad{linearlyDependentOverZ?([v1,...,vn])} returns true if the
+      ++ vi's are linearly dependent over the integers, false otherwise.
+    linearDependenceOverZ  : Vector R -> Union(Vector Z, "failed")
+      ++ \spad{linearlyDependenceOverZ([v1,...,vn])} returns
+      ++ \spad{[c1,...,cn]} if
+      ++ \spad{c1*v1 + ... + cn*vn = 0} and not all the ci's are 0, "failed"
+      ++ if the vi's are linearly independent over the integers.
+    solveLinearlyOverQ     : (Vector R, R) ->
+                                      Union(Vector Fraction Z, "failed")
+      ++ \spad{solveLinearlyOverQ([v1,...,vn], u)} returns \spad{[c1,...,cn]}
+      ++ such that \spad{c1*v1 + ... + cn*vn = u},
+      ++ "failed" if no such rational numbers ci's exist.
+
+  Implementation ==> add
+    import LinearDependence(Z, R)
+
+    linearlyDependentOverZ? v == linearlyDependent? v
+    linearDependenceOverZ   v == linearDependence v
+    solveLinearlyOverQ(v, c)  == solveLinear(v, c)
+
+@
+\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>>
+
+<<package LINDEP LinearDependence>>
+<<package ZLINDEP IntegerLinearDependence>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}