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.

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.

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

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…

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

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 Number. 

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:

(TableName) =>

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

Here is the result:

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.

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

Rename the new query from the default name to MatrixA.

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

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. 

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.

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.

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.

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.

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

= [Value] * [B.Value]

When you are done, click OK.

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.

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.

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.

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

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

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.

let
 fnPrepareMatrix = (TableName) =>
 
 let
  Matrix = Excel.CurrentWorkbook(){[Name=TableName]}[Content],
  #"Added Index" = Table.AddIndexColumn(Matrix, "Index", 1, 1),
  #"Unpivoted Other Columns" =
   Table.UnpivotOtherColumns(#"Added Index", {"Index"}, "Attribute", "Value"),
  #"Replaced Value" =
   Table.ReplaceValue(#"Unpivoted Other Columns",
    "Column","",Replacer.ReplaceValue,{"Attribute", "Value"}),
  #"Replaced Value1" =
   Table.ReplaceValue(#"Replaced Value","Column","",
    Replacer.ReplaceText,{"Attribute"}),
  #"Changed Type" = Table.TransformColumnTypes(#"Replaced Value1",
   {{"Attribute", Int64.Type}}),
  #"Renamed Columns" = Table.RenameColumns(#"Changed Type",
   {{"Attribute", "Column"}, {"Index", "Row"}})
 in
   #"Renamed Columns",
 
 MatrixA = fnPrepareMatrix("MatrixA"),
 MatrixB = fnPrepareMatrix("MatrixB"),

 #"Merged Queries" =
  Table.NestedJoin(
   MatrixA,{"Column"},
   MatrixB,{"Row"},"NewColumn",JoinKind.LeftOuter),
 #"Renamed Columns" = Table.RenameColumns(#"Merged Queries",
  {{"NewColumn", "B"}}),
 #"Expanded B" = Table.ExpandTableColumn(#"Renamed Columns", "B",
  {"Column", "Value"}, {"B.Column", "B.Value"}),
 #"Added Custom" = Table.AddColumn(#"Expanded B", "AB", each [Value] * [B.Value]),
 #"Grouped Rows" = Table.Group(#"Added Custom", {"Row", "B.Column"},
  {{"AB", each List.Sum([AB]), type number}}),
 #"Renamed Columns1" = Table.RenameColumns(#"Grouped Rows",
  {{"B.Column", "Column"}}),
 #"Pivoted Column" = Table.Pivot(
  Table.TransformColumnTypes(#"Renamed Columns1",
   {{"Column", type text}}, "en-US"),
   List.Distinct(Table.TransformColumnTypes(#"Renamed Columns1",
    {{"Column", type text}}, "en-US")[Column]), "Column", "AB")
in
 #"Pivoted Column"