To: J3                                                     J3/19-185
From: Van Snyder
Subject: Chained matrix multiplication
Date: 2019-July-26

The request for this work item arose as a result of discussions during
the ICIAM meeting in Valencia 15-19 July 2019, and the meeting of IFIP
Working Group 2.5 (Numerical Software) 20 July 2019.

Number
======

TBD

Title
=====

Chained matrix multiplication

Status
======

For consideration.

Basic functionality
===================

Allow the MATMUL intrinsic function to have up to 26 arguments.

Rationale
=========

Parenthesization of matrix products has a profound impact on
performance.  For example, in ABx, where A and B are NxN matrices and x
is an N-vector, (AB)x has N^3 complexity, while A(Bx) has N^2
complexity.

Consider the product ABCD, where the shapes of the matrices are [10,20],
[20,50], [50,2], [2,100], respectively.  The parenthesization (A(B(CD)))
requires 265,000 operations.  The parenthesization (A(BC)D) requires
22,000 operations.

Determining the optimal parenthesization is a simple dynamic-programming
problem, but producing a general procedure to handle an arbitrary number
of factors, of different kind and rank, is non-trivial for user
programs.  It would not be difficult for a processor to compute and
execute the optimal parenthesization if the MAMTUL intrinsic function
allowed an arbitrary number of arguments.

Estimated impact
================

Minor.  Description in the standard would be simple.  Determining
optimal parenthesization is a simple dynamic programming problem,
described (for example) in "The Design and Analysis of Algorithms" by
Aho, Hopcroft, and Ullman.  Once parenthesization is determined, the
processor could use existing methods.

Detailed specification
======================

Allow the MATMUL intrinsic function to have up to 26 arguments:

  MATMUL ( MATRIX_A, MATRIX_B [, MATRIX_C, ..., MATRIX_Z ] )

Rather than using optional arguments, several specific interfaces could
be provided, perhaps with fewer, say six arguments:

  MATMUL ( MATRIX_A, MATRIX_B )
  MATMUL ( MATRIX_A, MATRIX_B, MATRIX_C )
  MATMUL ( MATRIX_A, MATRIX_B, MATRIX_C, MATRIX_D )
  MATMUL ( MATRIX_A, MATRIX_B, MATRIX_C, MATRIX_D, MATRIX_E )
  MATMUL ( MATRIX_A, MATRIX_B, MATRIX_C, MATRIX_D, MATRIX_E, MATRIX_F )

Either all arguments shall be of numeric type, or all shall be of
logical type.  The size of the first (or only) dimension of an argument
after the first shall be equal to the size of the second (or only)
dimension of the previous argument.  At most one argument shall be of
rank one.

The effect is to multiply the arguments in the order specified.

Recommend that the processor determine an optimal parenthesization.