Faster Matrix Mulitplication

As a followup for our recent Matrix Multiplication post here, I would like to share with you a faster query for Matrix Multiplication (Faster only relative to the previous ones I shared. Excel is probably not the best tool for big matrices, and you may still need to use other tools such as R).

I would like to thank Imke Feldmann and Bill Szysz for sharing their queries. It turns out that the use of List.Generate is quite slow in comparison to the native Power Query transformations that we will share today.

Note: If you are an advanced Power Query practitioner, you can skip to the end of this blog to see the final M expression, and download the workbook sample.

Step-By-Step Tutorial for Matrix Multiplication query

Assuming we have two tables or named ranges MatrixA and MatrixB in our Excel workbook, we will start by importing MatrixA using Excel–>Data–>From Table in Excel 2016,  or Power Query–>From Table in Excel 2010, 2013 with the Power Query Add-In.

Screenshot_19

Our next series of transformation will reshape this table to a a new table of row,column, value columns.

Click the drop down menu Add Index Column in Add Column tab, then click on From 1.Screenshot_22

A new column will be added with the row index. We will select the new columnright click on its header, and click Unpivot Other Columns.Screenshot_23

The last Unpivot operation transforms our table into the desired row, column, value structure. We just need to perform few minor adjustments.

Next step is to change the values of the second column from “ColumnX” to the numeric value X. To do it select the second column, right click on its header and click on Replace Values…Screenshot_24

In The Replace Values dialog, type the word Column in Value To Find, keep Replace With edit box empty, and click OK.Screenshot_26

Now we will convert the values in the second column to numbers by right clicking the column header and selecting Change Type and then Whole NumberScreenshot_27

We can now rename the first and second columns to Row and Column respectively, and that finishes the transformation sequence that reshapes the original matrix into a row, column, value format.

We will now change our transformation into a function.

Let’s rename the query to PrepareMatrix, and Click Advanced Editor in Home tab, and add this first line into the M expression:

Next, we will find the line with the formula Excel.CurrentWorkbook and replace the text “MatrixA” with TableName.

Here is the result:

Screenshot_29

Click Done in the Advanced Editor.

In the Queries pane you will find the new query function PrepareMatrix. Right click on the function and click Invoke.

Screenshot_30

In the Enter Parameter dialog, type MatrixA in TableName (option), and click OK.Screenshot_31

Rename the new query from the default name to MatrixA.

Screenshot_32

Now for the second time, invoke the query function PrepareMatrix, type MatrixB in  TableName (optional), and click OK.Screenshot_33

Call the new query MatrixB.

At this stage we have two queries: MatrixA and MatrixB in the formats of row, column and value. The next step will be a tricky one. We will create a merged table in which each row contains a value from MatrixA that should be multiplied by a value from MatrixB in order to achieve matrix multiplication.

To better understand the next step, here is a mathematical observation about matrix multiplication:

A cell in row i and column j of MatrixA  will be multiplied by all the cells of row j in MatrixB. So if we join MatrixA and MatrixB by MatrixA columns and MatrixB rows, we can get a new table that contains all the pairs from the two matrices that are needed for the multiplication.

We will now select the query MatrixA and click Merge Queries in Home tab. Screenshot_34

In the Merge dialog select Column as the matching column of MatrixA, and then select MatrixB as the second table with Row as the matching column.

Keep the default Left Outer as Join Kind and click OK.Screenshot_35

At this stage you will encounter a Privacy warning. To overcome it open File–>Query Options and select the option Ignore the Privacy Levels…  Then click OK and Refresh Preview to get the merged results.Screenshot_36

Let’s rename the merged  column to B and expand it. In the expand pane select Column and Value, and keep the Use original column name as prefix checked. Click OK when you are done.Screenshot_37

Now we have a new table with all the combinations that are required for the multiplication of cells from MatrixA and MatrixB in the columns Value and B.Value.

To perform the actual multiplication, click Add Custom Column in Add Column tab.Screenshot_38

In the Add Custom Dialog type AB in New column name and type the formula below in Custom column formula box.

When you are done, click OK.

Screenshot_39

The next step is to perform all the sums of the multiplications by each row of MatrixA and columns of MatrixB.

Select the columns Row and B.Column and click Group By in tab Transform.Screenshot_40

In the Group By dialog, type AB as New column name, select Sum as Operation and enter the text AB as Column. Then click OK.Screenshot_41

This is nice. We now have a new table with all the cells of MatrixA * MatrixB. The final sequence of transformations will reshape this table into a normal matrix.

Screenshot_42

Select the second column (Column) and click Pivot Column in Transform tab.Screenshot_43

In Pivot Column dialog, select AB as Values Column and select Don’t Aggregate under advanced options. When you are done click OK.Screenshot_44

That’s it. We now have a faster matrix multiplication query. And we did it with 99% UI operations.

Final touch:

To rebuild the queries as a single query, you can move PrepareMatrix, MatrixA and MatrixB inside the main query. Here is the final expression.

 

 Download the workbook sample here.

Leave a Reply