[es] - Resavanje sistema linearnih jednacina

vbankovic
BG

Član broj: 51214
Poruke: 14
212.200.176.*

Profil

Resavanje sistema linearnih jednacina

^{04.04.2007. u 20:20}

Interesuje me da li neko zna, neki algoritam za resavanje sistema linearnih jednacina, ali onih gde je matrica sistema indefinitna i retka.
Moze i neka literatura na ovu temu. Hvala.

^{04.04.2007. u 20:20}

mcetina2
Marko Cetina
Grad student (fizika)
Cambridge, MA (SAD)

Član broj: 125398
Poruke: 220
*.MIT.EDU.

Profil

Re: Resavanje sistema linearnih jednacina

^{06.04.2007. u 07:05}

Pitanja:
1) kolika je matrica/problem?
2) da li je matrica sistema simetricna/hermitska?
3) odakle potice/kako glasi problem?
4) imas MATLAB?
5) cuo za BLAS?
6) cuo za ATLAS?
7) cuo za LAPACK?
8) iskustvo sa Fortranom?

Za n<=1e4 mozes da koristis rutine za ne-retke matrice u MATLAB-u. Mozda u Mathematici ali samo verzija >=5.
Za simetricne ili hermitske matrice dimenzije do 1e7 mozes da koristis conjugate gradient. Preconditioning helps. A lot. Da ponovim: PUNO.

Performanse ce zavisiti puno od odnosa najvece i najmanje sopstvene vrednosti matrice sistema (condition number of the matrix).
Ovo je glavni razlog zasto je preconditioning bitan. Preconditioning je glavni razlog zasto je bitno znati i razumeti konkretan problem. Seriously.

Za nesimetricne sisteme postoji biconjugate gradient. Nemam licnog iskustva sa doticnim ali sam razgovarao sa nekim ko ima. Iskustvo je bilo lose. Izrazito lose. Pouka: potrudi se da dovedes problem u Hermitian/symmetric formu.

*detaljna* referenca iz numericke analize je
http://www.amazon.com/Introduc...lied-Mathematics/dp/038797878X

odlicna referenca za numericku linearnu algebru je:
http://www.amazon.com/Computat...&qid=1175839017&sr=1-1

za brzinu koda bitna je optimizacija pristupa memoriji i cache-u. puno. SSE2/3 je dobra ideja. oba problema resavaju se koriscenjem optimizovanih BLAS ili ATLAS rutina za sve osnovne operacije nad vektorima i matricama.

znaj da je MATLAB tanak omot oko prilicno adekvatne (sto se koriscenja memorije tice) LAPACK/BLAS implementacije.
znaj da su zato MATLAB instrukcije prilicno brze.
znaj medjutim da je MATLAB scripting jezik:
a) ocajan
b) ocajno spor

Happy supercomputing,
Marko

^{06.04.2007. u 07:05}

vbankovic
BG

Član broj: 51214
Poruke: 14
195.252.79.*

Profil

Re: Resavanje sistema linearnih jednacina

^{06.04.2007. u 11:21}

Sistem nastaje kao posledica resavanja metodom konacnih elemenata, matrica je dimenzija 20000x20000, i nazalost nije simetricna. Ja sam mislio da implementiram neki postojeci algoritam u c++-u. Posto su mi knjige koje si mi preporucio nedostupne(cena), da li postoji neki besplatni strucni rad na ovu temu? Inace postoji specijalizovana biblioteka, ali je takodje preskupa.

^{06.04.2007. u 11:21}

mcetina2
Marko Cetina
Grad student (fizika)
Cambridge, MA (SAD)

Član broj: 125398
Poruke: 220
*.MIT.EDU.

Profil

Re: Resavanje sistema linearnih jednacina

^{06.04.2007. u 19:39}

Zasto finite element matrica nije simetricna? Da li se radi o elasticnosti ili nekom drugom problemu?
Intuicija mi je da energije potice od interakcije elemenata. A interakcije je simetricna.

Sto se biblioteka tice, ATLAS, BLAS i LAPACK su besplatni. Besplatna i je i gomila drugih biblioteka sa Netlib-a.
Znas za boost?
Takodje imas frameworks za finite elements u C++-u poput deal.II

Conjugate gradient sam sam koristio i nije tezak. Sa biconjugate gradientom kazem da mi je drug imao veoma lose iskustvo.

^{06.04.2007. u 19:39}