---

Hej!

Er der nogen der har erfaring med numeriske pakker, der kan
diagonalisere symmetriske og reele matricer, der er halvstore
dvs. 10000-100000 rækker og søjler?

Mit problem er Kirchoff matricer for tilfældige grafer, hvor
edges i netværket selv består af ~100 nodes af funktionalitet 2.

Dvs. det er 100-1000 blokke af 100x100 submatricer, hvor
submatricerne kun er triagonale. Og disse submatricer er
så koblet tilfældigt sammen i graf strukturen. Dette må kunne
danne grundlag for en smart optimering ved at repræsentere
netværks og submatrix egenrum separat?

Jeg vil gerne have egenværdi spektrummet, samt egenvektorer
(helst en efter en og ikke i en stor fed matrix der fylder
et par Gb;*)

Senere vil jeg gerne introducere offdiagonal blokke der er
konstante mellem forskellige submatricer for at simulere et
gennemsnit over det at nodes langs to edges er samme sted i
rummet, dvs. introducere en type af højre funktionalitets
nodes på par af edges og tvære denne ud over en vis længde
af en edge.

Matricerne vil for størstedelen bestå af 0 så et array af
doubles er nok ikke den mest praktiske repræsentation.

Rent praktisk er problemet en bead-spring model af et
polymer netværk. De enkelte edges i netværket er altså
enkelte polymere, der krydslinkes fx. i en vulkanisering
eller bestrålingsprocess, så der opstår en tilfældig
netværksstruktur.

Den native netværksmodel repræsentere kun effekter fra
forbundethed af nabobeads, så beads kan bevæge sig
gennemhinanden, virkelige polymere kan ikke krydsehinanden.
Ovenstående udtværingsprocess er en måde at repræsentere
effekten af at kæder vekselvirker med hinanden (slip-links),
der gør at kæden lokaliseres i rør omkring en eller anden
middel position.

Egenværdierne for netværkets Kirchof matrix bestemmer,
hvordan de reagere på eksterne felter, fx. mekanisk shear
eller oscillerende magnetiske felter. Så disse er specielt
interessante.

--
Mvh. Carsten Svaneborg
Hvilke softwarepatenter har du krænket idag?
Se http://www.softwarepatenter.dk

---

Carsten Svaneborg <See_organization@for_email.in.de> writes:

> Er der nogen der har erfaring med numeriske pakker, der kan
> diagonalisere symmetriske og reele matricer, der er halvstore
> dvs. 10000-100000 rækker og søjler?

Jeg har aldrig haft grund til at bruge andet end LAPACK¹ til numerisk
lineær algebra -- det er høj kvalitet og har rutiner de mest almindelige
matrixsymmetrier (bl.a. symmetrisk).

Der findes optimerede LAPACK biblioteker til de fleste platforme Intel,
Alpha, Sparc, MIPS etc. Dem er det nok smart at bruge, når dit problem
er forholdsvist stort.

¹ <http://www.netlib.org/lapack/>

---

Carsten Svaneborg <See_organization@for_email.in.de> writes:
> Er der nogen der har erfaring med numeriske pakker, der kan
> diagonalisere symmetriske og reele matricer, der er halvstore
> dvs. 10000-100000 rækker og søjler?

[meningsforstyrrende snip]

> Jeg vil gerne have egenværdi spektrummet, samt egenvektorer
> (helst en efter en og ikke i en stor fed matrix der fylder
> et par Gb;*)

[meningsforstyrrende snip]

Jeg har en ide som jeg ikke er helt sikker på, men læs alligevel. Så
vidt jeg har forstået er du ikke interesseret i at få fat i alle
egenværdierne. Du er kun interesseret i et søjlediagram over
egenværdierne. Med andre ord er det nok for dig at kunne spørge. Hvor
mange egenværdier er mindre end x.

Nu er det følgende frit efter hukommelsen, men så vidt jeg kan huske
er der noget med at hvis du LU dekomponerer, så ændrer du ikke
antallet af negative egenværdier. (Det er vist noget med Sylvesters
teorem). Hvis du starter med en matrice A, kan du LU dekomponere
matricen (A - x I) dette giver dig antallet af egenværdier der er
mindre end x.

Det største problem (udover min svigtende hukommelse) er at du måske
ikke udnytter at din matrice har mange nuller.

PS: Hvis du er interesseret så lån denne bog
@book{parlett80,
author = {N. Parlett},
title    = {The symmetric eigenvalue problem},
year    = 1980,
publisher = {Prentice-Hall}
}

PPS: Her er et svar som jeg engang fik af den store guru Peter spellucci
fra sci.math.num-analysis
http://groups.google.com/groups?selm=38298715.B5F06CE1%40ruc.dk&output=gplain

PPPS: Der er kommet sparse matrix support til octave, så nu er der
ingen undskyldning for at bruge matlab.
http://users.powernet.co.uk/kienzle/octave/index.html


--
Niels L Ellegaard http://dirac.ruc.dk/~gnalle/
Perioden for midlertidig opholdstilladelse: http://www.7aar.dk
Nedskæring i ulandsbistand: http://www.kan-det-passe.dk
Anmeldelser af diskoteker http://www.ms.dk/minoritet/disco/anmeldelser.htm

---

Niels Langager Ellegaard <gnalle@ruc.dk> writes:
> Nu er det følgende frit efter hukommelsen, men så vidt jeg kan huske
> er der noget med at hvis du LU dekomponerer, så ændrer du ikke
> antallet af negative egenværdier.

Hmm det var vist noget vrøvl. Jeg prøver lige igen. Vi tager din
matrice A, og skriver den som produkt af en lower triangle L ( med 1 i
diagonalen) og en upper triangle U.

A = LU

Da gælder

Antallet af negative diagonalelementer som U er lig den samlede
multiplicitet af negative egenværdier i A

Antallet af positive diagonalelementer som U er lig den samlede
multiplicitet af positive egenværdier i A

Antallet af nul-diagonalelementer som U er lig den samlede
multiplicitet af egenværdien 0 i A

Givet et reeelt tal x kan vi definere B = A - x I. Vi finder L og U
således at

B - x I = LU

Da gælder

Antallet af negative diagonalelementer som U er lig den samlede
multiplicitet af egenværdier i B der er mindre end x

Antallet af positive diagonalelementer som U er lig den samlede
multiplicitet af egenværdier i B der er større end x

Antallet af nul-diagonalelementer som U er lig den samlede
multiplicitet af egenværdien x i B

--
Niels L Ellegaard http://dirac.ruc.dk/~gnalle/
Perioden for midlertidig opholdstilladelse: http://www.7aar.dk
Nedskæring i ulandsbistand: http://www.kan-det-passe.dk
Anmeldelser af diskoteker http://www.ms.dk/minoritet/disco/anmeldelser.htm

---

Niels Langager Ellegaard wrote:
> B - x I = LU
> Da gælder
:

Tak! Det vidste jeg ikke men det praktisk at vide.

I mit problem vil jeg gerne udregne et gennemsnit af
funktioner, der afhænger af egenværdier af Kirchoff
matricer, hvor gennemsnittet tages over netværkets
topologi dvs. Kirchoff matricer der opfylder visse
krav.

Dit forslag ville give mig en let måde at udregne
den integrerede egenværdi fordeling.

P (r) = integral P(lamda) d(lamda)
< -oo til r

For mit problem er P<(r) dog kvasikontinuert. Det
betyder numerisk at jeg skal sample den for mange r, og
jeg ved ikke om det er holdbart (matematisk og numerisk)
at partielt integrere denne diskontinuerte fordeling for
at udregne

<f(x)> = <sum_i f(x,lambda_i)>_topologi
= integral f(x,lambda) p(lambda) lambda
= - integral df/dr(x,r) p_<(r) dr.

En eksplicit liste af egenværdier for et ensemble af
statistisk uafhængige topologier, gør det muligt at
udregne ikke kun <f(x)> men også usikkerheden af denne.

Error propagation gennem integralet lyder som et maridt.

Jeg kunne generere sådan et ensemble ved en MC algortme
der lokalt piller ved netværkets topologi, det burde
betyde at diagonaliseringsmatricen også kun ændres lidt,
hvilket kunne udnyttes numerisk ved iterative
diagonaliserings algoritmer.

--
Mvh. Carsten Svaneborg
Hvilke softwarepatenter har du krænket idag?
Se http://www.softwarepatenter.dk

---

Niels Langager Ellegaard wrote:
> Jeg har en ide som jeg ikke er helt sikker på, men læs alligevel. Så
> vidt jeg har forstået er du ikke interesseret i at få fat i alle
> egenværdierne. Du er kun interesseret i et søjlediagram over
> egenværdierne. Med andre ord er det nok for dig at kunne spørge. Hvor
> mange egenværdier er mindre end x.

Spektrummet er en blanding af diskrete og kontinuerte fordelinger,
så din P(l)dl funktion er ikke kontinuert hvilket er en kedelig
egenskab.

Desværre skal jeg også summe over egenværdier i interessante
funktioner. Og et spørgsmål er netop hvad der sker med egenværdi
spektrummet og disse funktioner hvis N-> oo.

Men jeg vil spekulere noget mere over det.

> Nu er det følgende frit efter hukommelsen, men så vidt jeg kan huske
> er der noget med at hvis du LU dekomponerer, så ændrer du ikke
> antallet af negative egenværdier.

Negative egenværdier bør ikke findes. Fordi de svarer ikke
til relakation men eksplosion. (at de aligevel findes skyldes
at en hydrodynamisk preaverageing approximation bliver ugyldige
i visse tilfælde, men det er en anden kedel med fisk.)

> PS: Hvis du er interesseret så lån denne bog
> @book{parlett80,
> author = {N. Parlett},
> title = {The symmetric eigenvalue problem},
> year = 1980,
> publisher = {Prentice-Hall}
> }
Vil kigge på den.

--
Mvh. Carsten Svaneborg
Hvilke softwarepatenter har du krænket idag?
Se http://www.softwarepatenter.dk

---

Scripsit Carsten Svaneborg <See_organization@for_email.in.de>
> Niels Langager Ellegaard wrote:

> > Nu er det følgende frit efter hukommelsen, men så vidt jeg kan huske
> > er der noget med at hvis du LU dekomponerer, så ændrer du ikke
> > antallet af negative egenværdier.

> Negative egenværdier bør ikke findes.

Sådan som jeg forstod Niels' indlæg var pointen at man ved at gøre
deher smarte ting ved matricen A-tI kan man finde antallet af
egenværdier for A der er henholdsvis større og mindre end t.

--
Henning Makholm "Check the sprog."

---

Carsten Svaneborg wrote:

> Hej!
>
> Er der nogen der har erfaring med numeriske pakker, der kan
> diagonalisere symmetriske og reele matricer, der er halvstore
> dvs. 10000-100000 rækker og søjler?
>
> Mit problem er Kirchoff matricer for tilfældige grafer, hvor
> edges i netværket selv består af ~100 nodes af funktionalitet 2.
>
> Dvs. det er 100-1000 blokke af 100x100 submatricer, hvor
> submatricerne kun er triagonale.

Matrixsparsitet udnyttes i pakkerne:
Arpack/Parpack (links i http://www.netlib.org/scalapack/
og SuperLu (http://www.nersc.gov/~xiaoye/SuperLU/ )
Har selv tidligere benyttet SuperLu på sparsematicer med
dimension omkring 1.000.000.


Med venlig hilsen
Jørn Hedegaard Povlsen

---

Carsten Svaneborg <See_organization@for_email.in.de> writes:
> Egenværdierne for netværkets Kirchof matrix bestemmer, hvordan de
> reagere på eksterne felter, fx. mekanisk shear eller oscillerende
> magnetiske felter. Så disse er specielt interessante.

Hmm nu hvor jeg er igang med de løse ideer, så har jeg lige et
spørgsmål til. Er du kun interesseret i lineære responsfunktioner? I
er det måske lettere at lave en simpel numerisk simulation af dit
modelsystem og derefter indsætte resultaterne i fluktuation -
dissipations theoremet.

--
Niels L Ellegaard http://dirac.ruc.dk/~gnalle/
Perioden for midlertidig opholdstilladelse: http://www.7aar.dk
Nedskæring i ulandsbistand: http://www.kan-det-passe.dk
Anmeldelser af diskoteker http://www.ms.dk/minoritet/disco/anmeldelser.htm

---

Niels Langager Ellegaard wrote:
> Er du kun interesseret i lineære responsfunktioner?
Nej.

> I er det måske lettere at lave en simpel numerisk simulation af dit
> modelsystem og derefter indsætte resultaterne i fluktuation -
> dissipations theoremet.

Det er det vi allerede gør, fx. en Langevin simulationer af netværk
af 2500 krydslinkede kæder af 100 beads hver, de kræver en god
mængde CPU'er at køre. Jeg har 50-100Gb af trajectory data fra
sådanne simulationer.

Det var derfor jeg var interesseret i om man kunne gøre det samme
analytisk og så løse den analytiske teori numerisk. Egenværdi
spektraet og funktioner deraf har også fundamental interesse
fordi det kan bruges til at undersøge effekten af forskellige
approximationer i de teoretiske modeller ifht. de observable man
sammenligner teorien med.

--
Mvh. Carsten Svaneborg
Hvilke softwarepatenter har du krænket idag?
Se http://www.softwarepatenter.dk