-A A +A

Auckland - Chained Matrix Multiplication

Primary tabs

Collection:   AlgoViz
Source: http://algoviz.org/node/989
Format:   Java Applet
Recommendation: Has Potential.
Description: This a visualization of chained matrix multiplication using dynamic programming to find the optimal multiplication ordering. The main page is a textual description of why finding an optimal ordering for matrix chain multiplication is important and some explanation of how it works. The visualization itself shows the assorted tables that need to be built and walks through the process of trying all of the combinations to find the lowest cost ordering. There are only four controls, 'stop', 'run, 'step', and 'skip'. The first three controls are exactly what one would expect, while the skip button jump to different stages of the algorithm based on the number of matrices in consideration (i.e., selecting skip as the first button, jumps forward to the end of computing the cost for all combinations of two matrices).
Evaluation: There is enough here that with a little effort a student could work out what the problem is and how this solution works. The visualization itself has promise, but it could be improved a great deal. There is a certain sloppiness to it that detracts from its effectiveness. The control buttons are all the wrong size, the the labels are all clipped to three letters. Some of the animation steps try to display several blocks of text, and they end up flashing on the screen without leaving the user time enough to read them. On the other hand, in an effort to really indicate where values come from, there is a fairly slow animation of the numbers sliding out of the table and into equations. Unfortunately, after a few frames of animation, the context is lost and while the number can still be seen traveling along, there is no indication where it came from. Simply highlighting the cell in the table would have been more effective. There are also a number of informative text messages that pop up in odd places, sometimes covering other parts of the display. Aesthetically, the visualization (and the website) is showing its age with the bold, multicolor approach common to the web in the 90's (particularly bad is the glaring yellow border on the visualization). I also would have liked it if the user had some control over the input data set. The data set that they have is a pretty reasonable one, but not being able to change it doesn't allow for much exploration.
Creator: John Morris  Woi Ang  
Publisher: University of Auckland  
Subject:   Algorithmic Techniques  Dynamic programming  
Language: english  
Relation: Morris' Collection  
ACM CCS 2012:
Human-centered computing Theory of computation Mathematics of computing Visualization Design and analysis of algorithms Mathematical analysis Theory and algorithms for application domains Algorithm design techniques Numerical analysis Algorithmic game theory and mechanism design Dynamic programming Computations on matrices