Showcasing straight-line programs with memory via matrix Bruhat decomposition

International Journal of Algebra and Computation, vol. 34, pp. 1059–1090

Abstract

We suggest that straight-line programs designed for algebraic computations should be accompanied by a comprehensive complexity analysis that takes into account both the number of fundamental algebraic operations needed, as well as memory requirements arising during evaluation. We introduce an approach for formalizing this idea and, as illustration, construct and analyze straight-line programs for the Bruhat decomposition of [Formula: see text] matrices with determinant 1 over a finite field of order q that have length [Formula: see text] and require storing only [Formula: see text] matrices during evaluation.

Authors 4

1. Alice C. Niemeyer Aachen Chair for Algebra and Representation Theory

   RWTH Aachen University

   Affiliation as printed

   Chair for Algebra and Representation Theory, RWTH Aachen University, Pontdriesch 10-16, Aachen 52062, Germany

2. Tomasz Popiel

   Monash University

   Affiliation as printed

   School of Mathematics, Monash University, 9 Rainforest Walk, Clayton, VIC 3800, Australia

3. Cheryl E. Praeger

   The University of Western Australia

   Affiliation as printed

   Centre for the Mathematics of Symmetry and Computation, The University of Western Australia, 35 Stirling Highway, Crawley, WA 6009, Australia

4. Daniel Rademacher Aachen Chair for Algebra and Representation Theory

   RWTH Aachen University

   Affiliation as printed

   Chair for Algebra and Representation Theory, RWTH Aachen University, Pontdriesch 10-16, Aachen 52062, Germany