Cholesky- vs. LR-Zerlegung

scipy

scipy ist eine Erweiterung von Python, welche die numpy Bibliothek um nützliche numerische Algorithmen ergänzt. Wir impotieren zunächste numpy und die linear Algebra Komponenten aus scipy:

import numpy
import scipy.linalg as linalg

Wir wollen:

import timeit

Anlegen einer symmetrisch-positiv-definiten Matrix:

print "Creating an s.p.d. matrix ... ",
n = 1000
Z = numpy.random.random((n,n))
A = numpy.dot(Z.transpose(),Z)
print "done"

Wir messen jetzt die Laufzeit der Cholesky Zerlegung, dafür verwenden wir den Befehl timeit.timeit. Als erstes übergeben wir einen unparametrisierten Funktionsaufruf, hierzu nutzen wir das Python-Konstrukt einer lambda-Funktion, um die Funktion direkt hier zu definieren. Als zweiten Parameter geben wir die Anzahl der Aufrufe an. Wir rufen die Cholesky Zerlegung:

N = 200

mal auf, um Messfehler zu reduzieren:

t = timeit.timeit(lambda: linalg.cholesky(A), number=N)

und geben die Laufzeit pro Iteration aus:

print "cholesky took %f seconds per call" % (t/N)

Als zweites vergleichen wir mit der Laufzeit der LR Zerlegung:

t = timeit.timeit(lambda: linalg.lu(A), number=N)
print "LU took %f seconds per call" % (t/N)

Und wie wir erwartet hatten sind die Laufzeiten der LR-Zerlegung etwas um den Faktor 2 höher als für die Cholesky Zerlegung.