Non-negative integer basis algorithms for linear equations with integer coefficients

DOI10.1007/BF00245019MaRDI QIDQ908692zbMATH OpenFDO

Authors Dallas Lankford

Publication date 1989

Published in Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00245019

zbMATH Keywords

computation of matricesunification

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Symbolic computation and algebraic computation (68W30)

Review text

Bei der Unifikation assoziativ-kommutativer Terme stellt sich die Frage nach einem effizienten Verfahren zur Aufzählung der Lösungsbasis für eine lineare homogene Gleichung in vielen Unbekannten mit ganzzahligen Koeffizienten. Dem bloßen Ausschöpfen von Restriktionen für die Basisvektoren [\textit{G. Huet}, Inform. Processing Letters 7, 144-147 (1978; Zbl 0377.10011)] werden hier konstruktive Verfahren gegenübergestellt, die auf sukzessives Ergänzen einer Matrix hinauslaufen, deren 1. Spalte alle Koeffizienten enthält; ergänzt wird die Matrix um reduzierte Summen von je 2 Zeilen. Verf. zeigt, daß dies Prinzip terminiert, sobald eine komplette Basis erschienen ist. Aus der Trennungseigenschaft der durch die lineare Gleichung definierten Hyperebene gewinnt er dann einen eleganten Mengenalgorithmus, der dem Ref. Fragen nach seiner Optimalität als reizvoll nahelegt. Messungen ergaben durchschnittlich die halbe Laufzeit des Ausschöpfungsverfahrens; die Beispiele, in denen letzteres ``beliebig gegen den neuen Algorithmus abfällt, lassen dessen genauere Laufzeitanalyse sogar dringlich werden.

Recommendations

• An elementary proof of the theorem that the most general matrix commutative with a given n-rowed square matrix involves at least n arbitrary parameters.
• scientific article; zbMATH DE number 3930334
• Actual solution of simultaneous linear numerical equations.
• Banded Eigenvalue Solvers on Vector Machines
• scientific article; zbMATH DE number 3872553
• scientific article; zbMATH DE number 3919641
• Asymptotically fast polynomial matrix algorithms for multivariable systems
• Untersuchung über Unabhängigkeitsbeweise nach der Matrizenmethode.
• scientific article; zbMATH DE number 741169
• scientific article; zbMATH DE number 49550

Cited in

(5)

• An algebraic approach to unification under associativity and commutativity
• Proving geometry theorems with rewrite rules
• AC-unification race: The system solving approach, implementation and benchmarks
• On Model Checking Boolean BI
• AC-termination of rewrite systems: a modified Knuth-Bendix ordering

This page was built for publication: Non-negative integer basis algorithms for linear equations with integer coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908692)