Dans ma classe de méthodes numériques le semestre dernier, j'ai implémenté l'élimination gaussienne en c ++ avec eigen et l'ai notée par rapport aux méthodes intégrées de eigen. Maintenant, pour mes camarades étudiants, j'essaye de traduire tous mes codes de c ++ / eigen à numpy, je me sens aussi (mal pensé) plus à l'aise avec numpy et python.

Cependant, ce code ci-dessous est plusieurs magnitudes plus lent au point où je suis sûr que j'ai fait une erreur. Pourtant, il ressemble exactement au code C ++.

Je pensais que c'était peut-être l'ordre de la ligne principale / principale de la colonne, mais cela n'a rien amélioré.

Si quelqu'un peut repérer mon erreur et signaler ce qui cause ce super ralentissement, je serais très reconnaissant.

def gauss_elimination(A, b, show_steps = True):
#A = np.asfortranarray(A)
n = A.shape[0]
Ab = np.zeros((n, n+1))
Ab[:,:n] = Ab[:, :n] + A
Ab[:, n] = b
if (show_steps):
    print(Ab)
#turn the matrix into step form
for i in range(n-1):
    pivot = Ab[i,i] #select pivot
    for row in range(i + 1, n):
        factor = Ab[row, i] / pivot #get factor
        if (show_steps):
            print(f"Subtracting {factor} times the {i} row from the {row} row")
        Ab[row, i:] = Ab[row, i:] - Ab[i, i:] * factor #subtract factor times previous row 
        #from current row after pivot column
        time.sleep(0.5)
        if(show_steps):
            print(Ab)
        
#backsubstituion
if (Ab[n-1, n-1] == 0):
    print("0 Pivot")
Ab[n-1, n] = Ab[n-1, n] / Ab[n-1, n-1]
for i in range(n-1)[::-1]: #traverse from the bottom row up
    for k in range(i+1, n): #iterate over found solutions so far
        Ab[i, n] = Ab[i, n] - Ab[k, n] * Ab[i, k] #subtract the solution x[k] times Ab[i, k] from solution column
        if (Ab[i, i] == 0):
            print("Pivot = 0")
        Ab[i, n] = Ab[i, n]/ Ab[i, i] #normalize i.e. get a leading one on the diag
#save solution
x = Ab[:, n]
if (show_steps):
    print(f"Solution \n {x.transpose()}")
return x
    

Merci!

0
Olli 13 mars 2021 à 11:46

1 réponse

Meilleure réponse

Si votre code python est environ 100 fois plus lent que C ++, ce n'est pas grave. Vous pouvez trouver des benchmarks sur le Web pour donner une idée de la vitesse de python par rapport au C ++ [1]

Notez que vous avez un time.sleep dans votre code. Suppression que votre fonction s'exécute en 15ms pour un 32x32.

Votre code a une complexité O(n^2) en python et O(n^3) opérations au niveau du processeur. Si vous testez avec n modéré, la surcharge de l'interpréteur python dominera. Au fur et à mesure que vous augmentez la taille de la matrice, vous commencez à obtenir moins de différence entre les deux temps d'exécution.

1
user12750353 14 mars 2021 à 14:31