Matrix operations over integral domains using nested APL

ABSTRACT

This paper deals with the use of APL to solve matrix theory problems with elements that are members of an integral domain. Two types of integral domains are used to illustrate the methods developed in this paper, integers (Z) and polynomials with real coefficients (Re[X]). However, the method of approach can be easily generalized to include other integral domains. APL2, due to its generalized data representations and rich functional semantics, was chosen to implement the solution to this problem. For each integral domain presented, a method of data representation is developed, and implementations of the necessary “primitive” functions (Addition, Multiplication, Division, and Comparison) are given. Finally, this newly developed system of functions and data representation is used to solve several of the most common Matrix Algebra problems. A simple recursive determinant and an implementation of Euclid's Greatest Common Divisor Algorithm are presented. Then, with these building blocks, a general algorithm for finding Smith's Canonical form and an algorithm to find the Invariant Factors are presented.

REFERENCES

• Rud85: Rudolph, Lu, CIS 680: Matrix Theory, Lecture Notes, Syracuse University, Fall 1985
• Smi65: Smiley, Maleolm F., Algebra of Matrices, Allyn and Bacon, Boston, MA, 1965

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Languages, Theory