Aufgabe:
a) Wieviele Körperoperationen brauchen Sie, um eine a × b-Matrix mit einer b × c-Matrix zu multiplizieren, wenn Sie als Multiplikationsalgorithmus die Definition des Matrixproduktes verwenden?
b) Sei ω ≥ 2 so, dass sich je zwei n × n-Matrizen mit O(nω) Operationen in K multiplizieren lassen. Zeigen Sie: dann lässt sich auch die Multiplikation einer n × 2n-Matrix mit einer 2n × n-Matrix mit O(nω) Operationen in K realisieren.
c) Für a, b, c ∈ N bezeichne T(a, b, c) die minimale Anzahl von Operationen in K, die nötig sind, um eine a × b-Matrix mit einer b × c-Matrix zu multiplizieren. Zeigen Sie: für alle a, b, c gilt T(a, b, c) = T(c, b, a).
Problem/Ansatz:
Zu a): Da habe ich O(abc), stimmt das?
Zu b): Da bin ich total verwirrt, bei mir kommt da immer etwas anderes raus als O(nω), zumindest wenn ich die normale Matrixmultiplikation nehme. Kann ich da auch eine andere nehmen? Weil Strassen & co geht ja nur für quadratische Matrizen. Auf jeden Fall bekomme ich immer bei den nxn Matrizen =(n3) und wenn ich 2n nehme O(n4). Was mache ich da falsch?
Zu c): Inwiefern muss ich mit T anders umgehen als mit O? O benutzt doch immer die maximale Anzahl, wenn ich es richtig verstanden habe. Und wie geht das dann für T? Für O könnte ich es leicht zeigen, aber bei T bin ich mir nicht sicher. Könnte mir da bitte jemand helfen?
Ich würde mich über jede Hilfe sehr freuen, da ich schon lange an der Aufgabe überlegt habe, aber es nicht ganz schaffe.
