A cubic time algorithm for finding the principal solution to Sylvester matrix equations over (max, +)

Abstract

We propose an algorithm for finding the so-called principal solution of the Sylvester matrix equation over max-plus algebra. The derivation of our algorithm is based on the concept of tropical tensor product introduced by Butkovič and Fiedler. Our algorithm reduces the computational cost of finding the principal solution from quartic to cubic. It also reduces the space complexity from quartic to quadratic. Since matrix–matrix multiplication is the most important ingredient of our proposed technique, we show how to use column-oriented matrix multiplications in order to speed-up MATLAB implementation of our algorithm. Finally, we illustrate our results and discuss the connection with the residuation theory.

Keywords:

• max-plus algebra
• principal solution
• Sylvester matrix equation
• tensor product

AMS Subject Classifications:

• 15A24
• 15A80

Acknowledgements

The authors would like to thank the referee for her/his very careful reading of the paper and many helpful suggestions.

Notes

1 In traditional linear algebra the correspondence between Sylvester matrix equations and linear systems of equations is well-known. See e.g. [12, Ch. 4].