Na przykładzie obliczania układu równań liniowych, można sprawdzić wydajność skryptu Ruby wraz z zastosowaniem biblioteki GSL.

Obliczenia numeryczne

Reprezentacja układu równań liniowych w metodach numerycznych, odpowiada macierzy n x n, zawierającej w każdym wierszu jedno równanie. Do wyliczenia wartości każdej z n-zmiennych, posłużę się dekompozycją LU. Główne założenie metody, polega na przecięciu macierzy m wzdłuż diagonali i wydzieleniu dwóch osobnych macierzy – górnej i dolnej. Takie podejście, pozwoli na znaczne przyśpieszenie procesu wyliczenia wartości zmiennych ¹.

Szczegółowe informacje dotyczące metody LU lub bardziej zaawansowanych, które są zawarte we wrapperze GSL do Ruby, można przeczytać tutaj ²

W pierwszym kroku, należy zadeklarować przestrzeń dla układu równań, oraz dla przykładu, zapełnić ją losowymi wartościami

n = 3
#deklaracja macierzy o wymiarach n x n
m = GSL::Matrix.alloc(n,n)

#zapelnienie losowymi danymi
n.times do |i|
 n.times do |j|
 m.set(i,j,rand)
 end
end

 puts "macierz:"
 m.print

po wykonaniu powyższego kodu, otrzymamy przykładową macierz:

macierz:
[ 1.953e-01 2.512e-01 1.112e-02
...
... ]

Następnie, należy zadeklarować wektor wyrazów wolnych b:

b = GSL::Vector::alloc(n)
n.times do |i|
 b.set(i, rand)
end

po wykonaniu, wektor będzie wyglądał tak jak na poniższym listingu

GSL::Vector
[ 1.523e-01 3.412e-02 ... ]

Mając gotowy zestaw zmiennych i przestrzeni, można przystąpić do właściwej operacji, czyli dekompozycji LU oraz obliczenia wartości zmiennych z układu równań.

lu, perm = m.LU_decomp
x = LU.solve(lu, perm, b)

puts "rozwiazanie:"
p x

puts "sprawdzenie:"
p m*x.col

Po poprawnym wykonaniu skryptu, otrzymamy wyniki w postaci wektora rozwiązań oraz wektora sprawdzającego wynik.

rozwiazanie:
GSL::Vector
[ 5.710e-01 3.841e-01 3.949e-01 ]

sprawdzenie
GSL::Vector::Col
[  8.056e-01
 3.803e-01
 5.894e-01 ]

Wydajność i czas wykonywania

Powyższa metoda rozwiązywania układu równań liniowych, może być ciekawym narzędziem do badania jak zmienia się wydajność i czas wykonywania obliczeń wraz ze wzrostem ilości danych. Poniższy program będzie zwiększał rozmiar macierzy m (za każdym obrotem o jeden) oraz zwracał czas wykonywania. Testowanie czasu będzie możliwe dzięki klasie Benchmark ³

#podłączanie wymaganych bibliotek i klas

require("gsl")
include GSL
include Linalg
require 'benchmark'

#rozmiar n x n macierzy
xx = 500

#stan początkowy licznika
n = 1
#uruchomienie pętli, która za każdym razem zwiększy rozmiar macierzy

xx.times do

puts" n = "+n.to_s
#deklaracja macierzy
m = GSL::Matrix.alloc(n,n)

#zapelnienie losowymi danymi
n.times do |i|
 n.times do |j|
 m.set(i,j,rand)
 end
end

puts "macierz:"
m.print

#deklaracja wektora
@@b = GSL::Vector::alloc(n)

n.times do |i|
 @@b.set(i, rand)
end

puts "wyrazy wolne:"
p @@b

Benchmark.bm(7) do |x8|
 x8.report("LU_decomp:") { @@lu, @@perm = m.LU_decomp }
 #x8.report("LU_solve: ") { @@x = LU.solve(@@lu, @@perm, @@b) }
end

puts "rozwiazanie:"
p @@x

p m*@@x.col
n=n+1
end

Zastosowanie zmiennych globalnych (oznaczonych przez symbol @@), pojawia się tutaj dlatego, ponieważ inaczej nie udało mi się przekazać wartości zmiennej z pętli mierzącej wydajność. Być może, istnieje bardziej profesjonalne rozwiązanie takiego problemu, jednak do tego przykładu, wybrane podejście spełnia dobrze swoje zadanie.
W wyniku uruchomienia skryptu, otrzymamy następujące wyniki

$ ruby LU.rb
 n = 1
 user  system      total        real
LU_decomp:  0.000000   0.000000   0.000000 (  0.000000)
LU_solve:   0.000000   0.000000   0.000000 (  0.000000)
 n = 2
 user     system      total        real
LU_decomp:  0.000000   0.000000   0.000000 (  0.000000)
LU_solve:   0.000000   0.000000   0.000000 (  0.000000)
 n = 3

....
LU_decomp:  2.534000   0.010000   2.544000 (  2.563000)
 n = 843

 user     system      total        real
LU_decomp:  2.534000   0.000000   2.534000 (  2.533000)
 n = 844
...

Na niskiej klasy sprzęcie testowym (CeleronM@1ghz, 2GB ram, winxp), wyraźne opóźnienia w obliczeniach pojawiają się już (lub dopiero) przy rozmiarach n = 800.

Na poniższym wykresie, widać zależność czasu dekompozycji macierzy do jej rozmiaru.

Inne przykłady badania wydajności, można znaleźć w ciekawym artykule, opublikowanym na skorks.com ⁴

Tags: benchmark, dekompozycja LU, GSL, macierz, obliczenia numerzyczne, Ruby, układ równań

This entry was posted on Sunday, May 23rd, 2010 at 22:34 and is filed under Inne, Programowanie, Ruby. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.