Rys. 1

Każdy student matematyki, informatyki lub politechniki na pierwszym roku poznaje wzór, który definiuje iloczyn macierzy: jeśli liczba kolumn macierzy  jest równa liczbie wierszy macierzy  to ich iloczynem jest macierz  której współczynniki to  Takie mnożenie macierzy jest znane od XIX wieku. Dopiero wiek później został wynaleziony sposób jego zobrazowania, który dla mnie jest wart tysiąca słów, a nawet trochę więcej.

Schemat Falka, bo tak się ten wynalazek nazywa, składa się z tabelek ze współczynnikami macierzy, rozmieszczonych jak na rysunku 1 Łatwo jest na nim odnaleźć współczynniki macierzy (na lewo) i  (powyżej), które mają wpływ na współczynnik  iloczynu. Wszystkie znane własności mnożenia macierzy mają, oczywiście, dowody rachunkowe. Schemat Falka pozwala zobaczyć wiele z tych własności, a to jest w pewnym sensie coś więcej niż dowód.

Rys. 2

Własność 1. Współczynniki nie muszą być liczbami, byleby można je było jakoś mnożyć, a iloczyny jakoś dodawać; w tym sensie definicja iloczynu macierzy jest uniwersalna. Na przykład (Rys. 2) współczynnikami mogą być macierze (zwane blokami), jeśli tylko „pasują”, tj. dla każdego  wszystkie bloki  mają tyle samo wierszy, dla każdego  wszystkie bloki  mają tyle samo kolumn, i dla każdego  każdy blok  ma tyle samo kolumn, ile bloki  mają wierszy. Jeśli bloki są macierzami liczbowymi, to mamy stąd ogólniejszy zapis mnożenia macierzy liczbowych. Można też rozpatrywać bloki puste, tj. mające 0 wierszy lub kolumn, co czasami jest wygodne.

Rys. 3

Własność 2. O macierzy  mówi się, że jest trójkątna górna, jeśli wszystkie jej współczynniki  takie że  są równe  Mnożenie macierzy ma tę własność, że jeśli obie macierze  i   są trójkątne górne, to ich iloczyn też jest taki. Spójrzmy na rysunek 3: po odnalezieniu współczynników w  -tym wierszu macierzy  i  -tej kolumnie macierzy  zauważamy, że jeśli  to w każdym iloczynie  co najmniej jeden czynnik jest zerem, a stąd  Analogiczna własność dotyczy macierzy trójkątnych dolnych (takich że  dla ), co proponuję Czytelnikom narysować własnoręcznie.

Rys. 4

Własność 3. Transpozycja przyporządkowuje dowolnej macierzy  o współczynnikach  macierz  o współczynnikach ; inaczej mówiąc, przekształcenie to zamienia wiersze z kolumnami. Jeśli macierze  i   można pomnożyć (i mnożenie współczynników jest przemienne), to  Ze schematu Falka to wynika natychmiast po narysowaniu jego odbicia symetrycznego względem ukośnej linii (tzw. diagonali macierzy ), porównaj rysunki 1 i 4. Mnożenie macierzy (bloków) nie jest przemienne, dlatego dokonując transpozycji iloczynu macierzy zbudowanych z bloków, tj. „odbijając” schemat Falka, musimy „odbić”, czyli transponować każdy blok macierzy  i   i ich iloczynu. Ale to po obejrzeniu rysunków jest oczywiste.

Własności 4 i 5. Macierz  jest diagonalna, jeśli wszystkie współczynniki oprócz  ma zerowe. Macierz permutacji jest to macierz kwadratowa, która w każdym wierszu i w każdej kolumnie ma jeden współczynnik równy  i pozostałe współczynniki  Wiersz -ty macierzy  gdzie macierz  jest diagonalna, jest iloczynem współczynnika  i  -tego wiersza macierzy  Jeśli zaś  jest macierzą permutacji, to iloczyn  powstaje przez poprzestawianie wierszy macierzy  Narysowanie schematów (najlepiej z użyciem bloków) i doprecyzowanie szczegółów polecam dla relaksu. A co będzie, jeśli to drugi (tj. prawy) czynnik jest macierzą diagonalną lub permutacji?

Rys. 5

Własność 6. Łączności mnożenia macierzy tak całkiem bez rachunków pokazać się nie da, ale zobaczmy schematy na rysunku 5 Jest jasne, że wymiary macierzy  i   są identyczne. Jeśli w miejsce  podstawimy blok -ty wiersz macierzy  i zastąpimy  przez -tą kolumnę,  to w obu przypadkach dostaniemy współczynnik na przecięciu -tego wiersza i  -tej kolumny odpowiedniego iloczynu wszystkich trzech macierzy. Wyróżnimy w macierzach bloki

Podstawiając tak podzielone macierze do pierwszego schematu, dostaniemy

a z drugiego schematu otrzymamy

Jeśli mnożenie mniejszych bloków jest łączne i rozdzielne względem dodawania, a dodawanie jest przemienne, to oba te wyrażenia mają tę samą wartość. Ale to umożliwia przeprowadzenie dowodu indukcyjnego, zaczynając od bloków pustych i bloków  tj. zbudowanych z pojedynczych współczynników.

Schemat Falka z blokowym przedstawieniem macierzy został wykorzystany do zilustrowania bardzo pięknego, równoległego algorytmu mnożenia dużych macierzy przy użyciu karty graficznej w architekturze CUDA; zachęcam do zapoznania się z nim w dokumentacji firmy NVIDIA. Tu zaś wykorzystamy schemat Falka do przedstawienia idei szybkiego (sekwencyjnego) algorytmu mnożenia wielkich macierzy rzadkich, czyli takich, których większość współczynników (np. ponad ) to zera. Iloczyn macierzy rzadkich zwykle też jest macierzą rzadką, a przy tym każdy (lub prawie każdy) jego niezerowy współczynnik jest sumą niewielu niezerowych składników. Dopuszczamy zupełnie dowolne rozmieszczenie niezerowych współczynników w macierzach  i   Chcielibyśmy, aby algorytm mnożył i dodawał tylko liczby różne od zera.

Rys. 6

Zobaczmy schemat na rysunku 6 W pokazanym przykładzie -ty wiersz macierzy  zawiera tylko trzy niezerowe współczynniki. Aby obliczyć -ty wiersz iloczynu, trzeba pomnożyć przez nie odpowiednie trzy wiersze macierzy  i dodać. Oczywiście, wystarczy odnaleźć i pomnożyć tylko niezerowe współczynniki macierzy  w tych wierszach.

Obie macierze i ich iloczyn będziemy reprezentować za pomocą wykazów niezerowych współczynników. Wykaz jest tablicą, której każdy element zawiera indeksy wiersza i kolumny oraz niezerowy współczynnik na ich przecięciu.

Porządkiem wierszowym wykazu współczynników macierzy nazwiemy taką kolejność jego elementów, że elementy reprezentujące niezerowe współczynniki z każdego kolejnego wiersza są obok siebie (a w obrębie wiersza elementy są uporządkowane dowolnie). W pierwszym kroku algorytmu należy (np. za pomocą sortowania) uporządkować w ten sposób wykazy obu macierzy,  i   Następnie tworzymy dwie tablice pomocnicze, których długości są o   większe od liczb wierszy tych macierzy. Kolejne elementy tablicy pomocniczej są indeksami uporządkowanego wykazu, umożliwiającymi szybki dostęp do elementów reprezentujących współczynniki każdego wiersza (liczba niezerowych współczynników w wierszu jest różnicą dwóch kolejnych indeksów w pomocniczej tablicy, jej ostatni element razem z przedostatnim umożliwia obliczenie liczby tych współczynników w ostatnim wierszu).

Aby obliczyć iloczyn  przeglądamy kolejne wiersze macierzy  Dla współczynnika  znajdujemy elementy reprezentujące niezerowe współczynniki w  -tym wierszu macierzy  Dla każdego takiego elementu, w dodatkowej tablicy, zapamiętujemy trójkę liczb: indeks elementu reprezentującego współczynnik  w wykazie  indeks elementu reprezentującego współczynnik  w wykazie  i indeks  odpowiedniej kolumny macierzy (czyli także iloczynu). Mając wszystkie takie trójki dla -tego wiersza macierzy (i iloczynu), sortujemy ich ciąg względem indeksów kolumn  Po tym posortowaniu łatwo jest odnaleźć odpowiednie współczynniki macierzy  i   i wykonać działania na nich, ponieważ iloczyny, których sumę trzeba obliczyć, są reprezentowane przez trójki znajdujące się obok siebie. W ten sposób otrzymamy niezerowe współczynniki w  -tym wierszu macierzy  a ściślej te współczynniki, które są sumami niezerowych składników.

Koszt tego algorytmu w istotny sposób zależy od użytego algorytmu sortowania, ale są znane bardzo szybkie algorytmy sortowania, których użycie sprawia, że obliczenia pomocnicze zabierają tylko kilka razy więcej czasu niż same działania na współczynnikach. Można też opracować podobny algorytm, korzystający z kolumnowego uporządkowania wykazów.

Rysunkowe przedstawienie mnożenia macierzy wymyślił w latach 50. dwudziestego wieku Sigurd Falk, profesor politechniki w Brunszwiku. Opisane wyżej przykłady nie wyczerpują zastosowań tego wynalazku, ale mam nadzieję, że uzasadniają jego wartość, przy użyciu kilku obrazków i w przybliżeniu 1100 słów.