= On 4 March 2012 11:45, Jussi Lehtola jussi.lehtola- -helsinki.fi <owner-chemistry%x%ccl.net> wrote:

Sent to CCL by: Jussi Lehtola [jussi.lehtola-*-helsinki.fi]
Hi,

does anyone know if there is an efficient and numerically stable way to
determine row and column indices of an element of a symmetric matrix,
for which only the storage index is known?

That is, the symmetric matrix A(i,j)=3DA(j,i) is stored in memory as
=A0A(i,j) =3D v[i*(i+1)/2 + j], i >=3D j

and now I'd like to determine what are i and j if I only know the index=
in v. This has to do with improving parallel scaling of the direct
formation of the (Hartree-)Fock matrix in ERKALE.

=A0<= /div>

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D
Ahmed E. Ismail
aei%x%= alum.mit.edu
aei%x%aya.yale.edu

--047d7b15b23535d9ad04ba6bdeeb-- From owner-chemistry@ccl.net Sun Mar 4 12:50:00 2012 From: "Jiabo Li jiaboli|yahoo.com" To: CCL Subject: CCL: A simple way to determine row and column indices for symmetric matrices? Message-Id: <-46418-120304124845-16928-rH6Mvcxb9vDNqqjUZsLyGg:+:server.ccl.net> X-Original-From: Jiabo Li Content-Type: multipart/alternative; boundary="-492277813-592154876-1330883318=:13336" Date: Sun, 4 Mar 2012 09:48:38 -0800 (PST) MIME-Version: 1.0 Sent to CCL by: Jiabo Li [jiaboli%%yahoo.com] ---492277813-592154876-1330883318=:13336 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable You can try this: =0A=C2=A0=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 SUBROUTINE DEC= ODEIJ(IJ,I,J)=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 IMPLICIT DOUBLE PRECISION (A= -H,O-Z)=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 I =3D INT(DSQRT(IJ+IJ+1.00000001D0= ))=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0J =3D IJ - I*(I-1)/2=0A=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 IF(J.GT.I) THEN=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0J =3D=C2=A0J - I=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0 I =3D I + 1=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 END IF=0A=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 RETURN=0A=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 END=0A=C2=A0=0AWher= e IJ is the index in your vector V, and I, J are the indexes in your 2D sym= metric matrix. =0A=C2=A0=0AIt is stable and relatively simple. =0A=C2=A0=0A= The above piece of code is from VB2000, a modern valence bond program. =0A= =C2=A0=0AJiabo Li=0A =0A=0A________________________________=0A From: "Ahmed= E. Ismail aei],[alum.mit.edu" =0ATo: "Li, Jiabo -= id#3p9-" =0ASent: Sunday, March 4, 2012 6:45 AM=0ASubje= ct: CCL: A simple way to determine row and column indices for symmetric mat= rices?=0A =0A=0AYou could do it in log(N) operations, where N is the numbe= r of rows in the matrix. I'd precompute the partial sums=0A=0AS_i =3D sum_(= k <=3D i) (N - k - 1)=0A=0Awhich is a partial sum of the number of elements= in row k from row 1 to row k. (Adjust indices for zero-indexing as needed.= ) Then you can do a binary search of an arbitrary index in v, finding the r= ow number directly from the partial sum vector, and then the column index c= an be computed from the knowledge of the difference between the index and t= he partial sum. =0A=0AHowever, you may not need the matrix, particularly if= the number of rows is large=E2=80=94you could just do it by realizing that= you're reversing the sequence of pyramidal numbers 1, 3, 6, 10. So it shou= ldn't be too hard to write a formula to do this calculation instead. =0A=0A= =E2=80=94AEI=0A=0AOn 4 March 2012 11:45, Jussi Lehtola jussi.lehtola- -hels= inki.fi wrote:=0A=0A=0A>Sent to CCL by: Jussi L= ehtola [jussi.lehtola-*-helsinki.fi]=0A>Hi,=0A>=0A>=0A>does anyone know if = there is an efficient and numerically stable way to=0A>determine row and co= lumn indices of an element of a symmetric matrix,=0A>for which only the sto= rage index is known?=0A>=0A>That is, the symmetric matrix A(i,j)=3DA(j,i) i= s stored in memory as=0A>=C2=A0A(i,j) =3D v[i*(i+1)/2 + j], i >=3D j=0A>=0A= >and now I'd like to determine what are i and j if I only know the index=0A= >in v. This has to do with improving parallel scaling of the direct=0A>form= ation of the (Hartree-)Fock matrix in ERKALE.=0A>=0A=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=0AAhmed E. Ismail=0A= aei:_:alum.mit.edu=0Aaei:_:aya.yale.edu ---492277813-592154876-1330883318=:13336 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable

You can tr= y this:

  &= nbsp;   SUBROUTINE DECODEIJ(IJ,I,J)
    &n= bsp; IMPLICIT DOUBLE PRECISION (A-H,O-Z)
      = I =3D INT(DSQRT(IJ+IJ+1.00000001D0))
      = ;J =3D IJ - I*(I-1)/2
      IF(J.GT.I) THEN
=         J =3D J - I
&= nbsp;      I =3D I + 1
    = END IF
      RETURN
   = ;   END

Where IJ is the index i= n your vector V, and I, J are the indexes in your 2D symmetric matrix.

It is stable and relatively simple.

The above piece of code is from VB2000, a mode= rn valence bond program.

Jiabo Li

From: "Ahmed E. Ismail aei],[alum.mit.edu" <owner-chemis= try]*[ccl.net>
To: "L= i, Jiabo " <jiaboli]*[yahoo.com>
Sent: Sunday, March 4, 2012 6:45 AM
Subject: CCL: A simple way to determi= ne row and column indices for symmetric matrices?

=0A

You could do it in log(N) operations, where N is the number= of rows in the matrix. I'd precompute the partial sums

S_i =3D sum_(k <=3D i) (N - k - 1)

which is a partial sum = of the number of elements in row k from row 1 to row k. (Adjust indices for= zero-indexing as needed.) Then you can do a binary search of an arbitrary = index in v, finding the row number directly from the partial sum vector, an= d then the column index can be computed from the knowledge of the differenc= e between the index and the partial sum.

=0A

Howeve= r, you may not need the matrix, particularly if the number of rows is large= =E2=80=94you could just do it by realizing that you're reversing the sequen= ce of pyramidal numbers 1, 3, 6, 10. So it shouldn't be too hard to write a= formula to do this calculation instead.

=0A

=E2=80= =94AEI

On 4 March 2012 11:= 45, Jussi Lehtola jussi.lehtola- -helsinki.fi <owner-chemistry:_:ccl.net> wrote:
=0A

=0ASent to C= CL by: Jussi Lehtola [jussi.lehtola-*-helsinki.fi]
=0AHi,
=0A
=0A
= =0Adoes anyone know if there is an efficient and numerically stable way to<= br>=0Adetermine row and column indices of an element of a symmetric matrix,=
=0Afor which only the storage index is known?
=0A
=0AThat is, the= symmetric matrix A(i,j)=3DA(j,i) is stored in memory as
=0A A(i,j)= =3D v[i*(i+1)/2 + j], i >=3D j
=0A
=0Aand now I'd like to determi= ne what are i and j if I only know the index
=0Ain v. This has to do wit= h improving parallel scaling of the direct
=0Aformation of the (Hartree-= )Fock matrix in ERKALE.

=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
Ahmed E.= Ismail
aei:_:alum.mit.edu
aei:_:aya.yale.edu
=0A
=0A

---492277813-592154876-1330883318=:13336-- From owner-chemistry@ccl.net Sun Mar 4 16:57:00 2012 From: "Malgorzata Biczysko malgorzata.biczysko!A!sns.it" To: CCL Subject: CCL: IMAMPC2012, September 12-14, Pisa: high-quality research by young scientists - First call Message-Id: <-46419-120303172839-9030-fCiHbvz5e6DiYC1IRTpWYQ:-:server.ccl.net> X-Original-From: "Malgorzata Biczysko" Content-Type: multipart/alternative; boundary="----=_NextPart_000_00EC_01CCF995.5A636B10" Date: Sat, 3 Mar 2012 23:28:34 +0100 MIME-Version: 1.0 Sent to CCL by: "Malgorzata Biczysko" [malgorzata.biczysko]=[sns.it] This is a multi-part message in MIME format. ------=_NextPart_000_00EC_01CCF995.5A636B10 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable ####### IMAMPC 2012, First announcement ######### (apology for any = cross-posting) Dear Colleagues, It is our pleasure to announce the third edition of the International = Meeting on Atomic and Molecular Physics and Chemistry (IMAMPC2012) that = will be held in Pisa, Italy, from September 12 to September 14, 2012. http://imampc2012.sns.it/ =20 The meeting is intended to promote high-quality research carried out by = young scientists and, conceived from an interdisciplinary perspective, = brings together experimentalists and theoreticians from diverse fields, = such as: - Electronic Structure and Spectroscopy of Molecules in the gas phase, = condensed phases and at the gas/surface interfaces, - Macromolecules and Aggregates, - Structural Dynamics, Liquids, Nanomaterials, - Photo-reactivity and Photovoltaics, - Ultra-Cold Collisions, Quantum Control, Superfluid Helium = Nanodroplets. IMAMPC2012 will be held at the Scuola Normale Superiore in Pisa starting = > from Wednesday, September 12 (in the morning) till Friday, September 14 = (the afternoon). There will be 18 invited lectures (http://imampc2012.sns.it/speakers) = and in addition 28 contributed lectures and one poster session. Contributed lectures will be selected from the submitted abstracts. We encourage postdoctoral researchers, tenure-track fellows or those in = early years of a permanent position to apply and to submit abstracts for = oral or poster presentations. The third edition of the IMAMPC is co-organized by CoDECS COST Action = (http://codecs.sns.it). =20 Registration Registration fee will include attendance to the conference, book of = abstracts, coffee breaks, conference dinner, and ap=E9ritif during the = poster session. Early-bird registration: up to July, 30 2012 : Full fee: 130 Eur; = Student fee : 80 Eur Normal registration: after July, 30 2012: Full fee: 180 Eur; Student = fee: 120 Eur For additional information please visit the workshop website at: = http://imampc2012.sns.it/ Looking forward to seeing you in Pisa! Scientific Committee Cristina Puzzarini (chair) Chiara Cappelli (co-chair) Malgorzata Biczysko Mar=EDa Pilar de Lara-Castells Rita Prosmiti Nadja Sandig Andrea Simoni Local Organizing Committee Malgorzata Biczysko Chiara Cappelli Sonja Grubisic Monica Sanna Daniele Licari ------=_NextPart_000_00EC_01CCF995.5A636B10 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

####### IMAMPC 2012, First announcement = #########=20 (apology for any cross-posting)

Dear Colleagues,

It is our pleasure to announce the = third edition of=20 the International Meeting on Atomic and Molecular Physics and Chemistry=20 (IMAMPC2012) that will be held in Pisa, Italy, from September 12 to = September=20 14, 2012.
http://imampc2012.sns.it/
= ;
The=20 meeting is intended to promote high-quality research carried out by = young=20 scientists and, conceived from an interdisciplinary perspective, brings = together=20 experimentalists and theoreticians from diverse fields, such = as:

- Electronic Structure and Spectroscopy = of=20 Molecules in the gas phase, condensed phases and at the = gas/surface=20 interfaces,
- Macromolecules and Aggregates,
- Structural = Dynamics,=20 Liquids, Nanomaterials,
- Photo-reactivity and Photovoltaics,
- = Ultra-Cold=20 Collisions, Quantum Control, Superfluid Helium = Nanodroplets.

IMAMPC2012 will be held at the = Scuola Normale=20 Superiore in Pisa starting from Wednesday, September 12 (in the morning) = till=20 Friday, September 14 (the afternoon).

There will be 18 invited lectures (http://imampc2012.sns.it/speak= ers)=20 and in addition 28 contributed lectures and one poster = session.
Contributed=20 lectures will be selected from the submitted abstracts.
We encourage=20 postdoctoral researchers, tenure-track fellows or those in early years = of a=20 permanent position to apply and to submit abstracts for oral or poster=20 presentations.

The third edition of the IMAMPC is = co-organized by=20 CoDECS COST Action (http://codecs.sns.it).

Reg= istration

Registration fee will include = attendance to the=20 conference, book of abstracts, coffee breaks, conference dinner, and = ap=E9ritif=20 during the poster session.

Early-bird registration: up to July, 30 = 2012 : Full=20 fee: 130 Eur; Student fee : 80 Eur
Normal registration: after July, = 30 2012:=20 Full fee: 180 Eur; Student fee: 120 Eur

For additional information please visit the workshop website = at: http://imampc2012.sns.it/

Looking forward to seeing you in Pisa!

Scientific Committee

Cristina Puzzarini (chair)
Chiara Cappelli = (co-chair)
Malgorzata=20 Biczysko
Mar=EDa Pilar de Lara-Castells
Rita Prosmiti
Nadja=20 Sandig
Andrea Simoni

Local Organizing Committee

Malgorzata Biczysko
Chiara Cappelli
Sonja Grubisic
Monica=20 Sanna
Daniele Licari

------=_NextPart_000_00EC_01CCF995.5A636B10--