text:
# Schrödinger functional at 𝑁_f=-2Talk given by B. Gehrmann at Lattice 2001, Berlin

## 1 Introduction

The non-perturbative computation of the strong coupling constant $`\alpha _s`$ from hadronic scales to perturbative high energy scales is one of the main interests of the ALPHA collaboration. For this computation, a finite volume renormalization scheme is used in which the coupling runs with the space-time volume . The scale evolution of the coupling is computed recursively with the help of the step scaling function, which is an integrated variant of the beta function for finite changes of the scale. Furthermore, Schrödinger functional boundary conditions and $`\mathrm{O}(a)`$ improvement are employed. An important property of the step scaling function is that it can be calculated by simulating pairs of lattices with different sizes $`L`$ for the same $`a`$ and taking the continuum limit.

After this programme had been successfully used in the quenched approximation , first results for full QCD with two flavors are now available . Unfortunately, full QCD is notoriously costly to simulate, and thus the data for the step scaling function do not reach very close to the continuum limit. In order to learn more about the extrapolation to the continuum and about the effect of $`\mathrm{O}(a)`$ improvement, we have studied the step scaling function in a Yang-Mills theory coupled to a bosonic spinor field, which has a local interaction and is therefore much cheaper to simulate. It corresponds to setting the number of flavors $`N_\mathrm{f}=2`$ in the partition function, and is therefore closely related to full QCD in perturbation theory. In the literature, this model is known as *bermion model* . Our focus here however is not on extrapolating results from negative to positive flavor number.

## 2 Bermion model

For a detailed discussion of the lattice setup, boundary conditions and the algorithm we have used, we refer to  and references therein.

The Schrödinger functional, as the partition function of the system, is an integral over all gauge and quark fields which fulfill the given boundary conditions. After integrating out the quark fields, it is

$`Z=e^\mathrm{\Gamma }`$ $`=`$ $`{\displaystyle D[U]D[\overline{\psi }]D[\psi ]e^{S[U,\overline{\psi },\psi ]}}`$ (1)
$`=`$ $`{\displaystyle D[U]e^{S_g}det(M^{}M)^{N_\mathrm{f}/2}}`$
with a gauge action $`S_g`$. For $`N_\mathrm{f}=2`$, the determinant can be written as

$$Z=D[U]D[\varphi ^+]D[\varphi ]e^{S_gS_b},$$
(2)
with a now local bosonic action

$$S_b[U,\varphi ]=a^4\underset{x}{}|(M\varphi )(x)|^2.$$
(3)
The fields $`\varphi (x)`$ carry color and Dirac indices.

We have chosen the bulk improvement coefficient $`c_{\mathrm{sw}}`$ by extrapolating the non-perturbative data for $`N_\mathrm{f}=0`$  and $`N_\mathrm{f}=2`$  in $`N_\mathrm{f}`$. An explicit calculation of $`c_{\mathrm{sw}}`$ along the lines of these references for the most critical parameters in our simulations has proven a good accuracy of this extrapolation. The boundary improvement coefficients $`c_t`$ and $`\stackrel{~}{c}_t`$ have been set to their perturbative values.

As the improved bosonic action depends quadratically on each link $`U_{x\mu }`$ through the clover term, it is difficult to employ finite step size algorithms such as the combination of heatbath and overrelaxation steps used in . Because of the large additional cost of hybrid Monte Carlo algorithms, we have decided to use global heatbath steps for the bosonic fields and local overrelaxation steps with respect to the unimproved action for the gauge fields. The clover term is taken into account by an acceptance step. The acceptance rate has turned out to be high enough (about 70 %) for such an approach. Nevertheless, there is a significant overhead due to the calculation of the action difference necessary for the acceptance step, resulting in a cost factor of about $`12`$ compared to unimproved Wilson bermions. On the other hand, comparing with data from , improved bermions are about a factor of $`10`$ cheaper than dynamical fermions, with a better scaling in $`a`$. In figure 1 we see a scaling of the cost with $`a^{2.5}`$.

## 3 Results

We have computed the step scaling function $`\mathrm{\Sigma }(u,a/L)`$ for the couplings $`u=\overline{g}^2=0.9793`$ and $`u=1.5145`$ and lattice sizes $`L=4,5,6,8`$. Most simulations were done on APE100 parallel computers with up to 256 nodes with 50 MFlops each. For the simulation of the largest lattice $`L/a=16`$ at $`u=1.5145`$ we have also used a crate of APEmille.

Figure 2 shows the results for the step scaling function plotted against $`(a/L)^2`$. Within the error bars, no linear dependence an $`a/L`$ is visible, and therefore an extrapolation linear in $`(a/L)^2`$ is justified. The extrapolated values are consistent with perturbation theory, and their error bars are of the same size as the perturbative 3-loop contribution.

In , the step scaling function was already computed in the unimproved bermion theory for $`u=0.9793`$. Figure 3 shows these results together with the data after implementing improvement. The linear cutoff effects for this observable are of the order of a few percent. In the plot, both data sets are fitted under the constraint of universality, i.e. that their continuum limit agrees. This fit is linear plus quadratic in $`a/L`$ for the Wilson bermion data and quadratic in $`a/L`$ in the improved data. Although the additional input from the Wilson data is included, the joint continuum limit $`\sigma _{\mathrm{combined}}(0.9793)=1.1059(43)`$ is almost the same as the value $`\sigma _{\mathrm{improved}}(0.9793)=1.1063(46)`$. A linear plus quadratic fit in $`a/L`$ of the unimproved data alone would have given the continuum result $`\sigma _{\mathrm{unimproved}}(0.9793)=1.103(12)`$.

This indicates a success of the improvement programme. The main contribution to the cost for the calculation of $`\sigma (u)`$ comes from the largest lattice. When using an improved action, the lattice size needed for a reliable extrapolation to the continuum is smaller than without improvement. Even in the model used here, where the algorithmic implementation implies a large overhead for the inclusion of the clover term, this leads to the improved case being more cost effective. In simulations with dynamical fermions and algorithms like Hybrid Monte Carlo, the implementation of a clover term is possible with much lower overhead, and the advantage should therefore be higher.

Acknowledgements. We would like to thank Peter Weisz for essential checks on our perturbative calculations and Rainer Sommer for helpful discussions. DESY provided us with the necessary computing resources and the APE group contributed their permanent assistance. This work is supported by the Deutsche Forschungsgemeinschaft under Graduiertenkolleg GK 271 and by the European Community’s Human Potential Programme under contract HPRN-CT-2000-00145.


format: text

text:
# Understanding chiral symmetry breaking with the overlap action

## Abstract

A chiral fermion action allows one to do very clean studies of chiral symmetry breaking in QCD. I will briefly describe how to compute with the overlap action (relatively) cheaply, and then turn to physics: Low modes of the Dirac operator show a “lumped” chiral density which peaks at the locations of instantons and anti-instantons. These modes dominate correlation functions at small quark mass in many channels. The picture qualitatively (and in some cases quantitatively) resembles an instanton liquid model.

Instantons are a plausible candidate for the source of chiral symmetry breaking. Would-be fermion zero modes sitting on individual instantons mix into a band, and the density of low modes is connected to the chiral condensate via the Banks-Casher relation. An elaborate phenomenology built on the interactions of fermions with instantons can account for many of the low energy properties of QCD . But is this picture true?

In principle, lattice simulations can address this issue. However, the usual lattice fermion actions themselves distort chiral symmetry. This can cloud the lattice results, since what is observed might just be due to the bad behavior of the action. Lattice actions which implement an exact chiral symmetry without doubling (namely, the overlap action ) allow one to study these questions in a theoretically clean context. This note describes recent work by Anna Hasenfratz and me, studying chiral symmetry breaking using an overlap action.

A generic overlap operator is

$$D(0)=x_0(1+\frac{z}{\sqrt{z^{}z}})$$
(1)
where $`z=d(x_0)/x_0`$ and $`d(m)=d+m`$ is some massive nonchiral Dirac operator for mass $`m`$. My choice of “kernel” $`d`$ is an action with nearest and next-nearest neighbors and fat links as a gauge connection, designed to “look like” an overlap action. I find eigenmodes of the squared Dirac operator $`D^{}D`$ using a conjugate gradient routine. This algorithm takes a set of trial vectors and iteratively improves them (with many multiplications of trial vectors by $`D^{}D`$). Any way it is implemented, an overlap action is much more expensive to use than a non-overlap action. The crucial trick I use to speed up the calculation is to begin the computation of eigenmodes of $`D^{}D`$ with eigenmodes of $`d(0)^{}d(0)`$. If these modes are close to eigenmodes of $`D^{}D`$, fewer iterations are needed. This can give a gain of up to a factor of 20 in time needed to find eigenvectors, compared to the cost of finding eigenmodes of the overlap with $`d`$ given by the Wilson action. In principle this would work for any action, but in practice I could not discover a good approximation to begin the calculation of eigenmodes of the overlap with Wilson or clover kernels.

All of the studies reported here were done in quenched approximation at $`\beta =5.9`$ (lattice spacing 0.11-0.13 fm), on $`12^4`$ and $`12^3\times 24`$ lattices.

We  collected a set of eigenmodes, extracted the local chiral density $`\omega (x)=\psi (x)|\gamma _5|\psi (x)`$ for each mode, and measured autocorrelation functions $`C_{\omega \omega }(r)=\omega (r)\omega (0)`$ and correlators of the chiral density with the topological charge density $`Q(r)`$ (as measured from a pure gauge observable), $`C_{\omega Q}(r)=\omega (r)Q(0)`$. All modes showed a strong peaking in both correlators at small $`r`$. Chiral zero modes “sit” on one sign of bumps of topological charge, while nonchiral fermion modes are localized on both signs of topological charge. As the fermion eigenvalue rises, these correlations slowly die away, but they persisted out to eigenvalues of 500 MeV or so. An example of a chirality autocorrelator is shown in Fig. 1.

We could extract a density profile from the shape of the bumps. Interpreting this profile a being due to a mixture of fermion zero modes sitting on instantons, we infer a typical instanton radius of $`\rho 0.3`$ fm, a familiar number from instanton phenomenology.

But are these few modes (typically 10-20 out of $`12^5`$) important? That is a qualitative question, but it is relevant to phenomenology. To test this, we constructed quark propagators “exactly,” and propagators truncated to include only a few low eigenmodes. We then looked at ordinary $`\stackrel{}{k}=0`$ propagators (as would be used in spectroscopy). I also computed  point-to-point correlators,

$$\mathrm{\Pi }_i(x)=\mathrm{Tr}J_i^a(x)J_i^a(0).$$
(2)
In the latter case it is customary to divide out by the free field correlator $`\mathrm{\Pi }_i^0(x)`$ and measure

$$R_i(x)=\mathrm{\Pi }_i(x)/\mathrm{\Pi }_i^0(x).$$
(3)
When the quark mass was small enough (pseudoscalar/vector mass ratio 0.5 or less), a few modes were sufficient to saturate the pseudoscalar and scalar correlators. This was not the case for the vector or axial channels. Baryon channels are noisy, but low modes seemed to make a substantial contribution there, too. What we saw was basically consistent with instanton liquid phenomenology: channels with spin-0 $`q\overline{q}`$ pairs or diquarks are supposed to couple strongly to instantons, as the pair propagates by hopping from instanton to instanton. Presumably this means that quark eigenmodes which are most sensitive to topology dominate the correlator. In channels with spin-1 diquarks or $`q\overline{q}`$ pairs, the fermions cannot couple to the same instanton, suggesting that low modes do not saturate their correlators.

As one example among many, consider the the correlator ratios $`R_{V+A}`$ and $`R_{VA}`$. In the sum rule/operator product expansion approach $`R_{V+A}`$ is dominated by perturbative physics and is expected to take a value very close to unity, while $`R_{VA}`$ is zero at small $`x`$ and receives only nonperturbative contributions which are relevant to chiral symmetry breaking. A comparison of full and low mode truncated correlators (at $`m_{PS}/m_V0.5`$) is shown in Figs. 2 and 3. Where phenomenology expects instanton-sensitive modes, there they dominate.

An extrapolation of this lattice data to zero quark mass is in reasonably good agreement with an instanton model  and with tau-decay data.

Finally, in Fig. 4 I show a comparison of several pionic matrix elements computed with complete quark propagators and from quark propagators truncated to the lowest 20 eigenmodes of $`D`$. Shown are the PCAC quark mass (from the divergence of the axial vector current), $`f_\pi `$, and $`f_5=0|\overline{\psi }\gamma _5\psi |\pi `$. Low modes make a large contribution to these observables.

To conclude: Low modes of fermions show structure which is strongly reminiscent of the expectations of instanton liquid models. Low modes show a peaked chirality density correlated with gauge field topology. These low modes contribute strongly in the pseudoscalar channel and other places where chiral symmetry is important, when the quark mass is small. It seems that instantons are connected, after all, with chiral symmetry breaking.

This work was supported by the US Department of Energy.


text:
# Teaching Parallel Programming Using Both High-Level and Low-Level Languages

## 1 Introduction

Parallel processing, the method of having many small tasks solve one large problem, has emerged as a key enabling technology in modern computing. The past several years have witnessed an ever-increasing acceptance and adoption of parallel processing, both for high-performance scientific computing and for more “general-purpose” applications. The trend was a result of the demand for higher performance, lower cost, and sustained productivity. The acceptance has been facilitated by two major developments: massively parallel processors and the widespread use of clusters of workstations.

In the last ten years, courses on parallel computing and programming have been developed and offered in many institutions as a recognition of the growing significance of this topic in computer science . Parallel computation curricula are still in their infancy, however, and there is a clear need for communication and cooperation among the faculty who teach such courses.

Georgia State University (GSU), like many institutions in the world, has offered a parallel programming course at the graduate and Senior undergraduate level for several years. Low-level languages and tools that have been used at GSU for the course included Parallel Virtual Machine (PVM) and Message Passing Interface (MPI) on an SGI Origin 2000 shared memory multiprocessor system. As we all know, the message passing paradigm has several disadvantages: the cost of producing a message passing code may be between 5 and 10 times that of its serial counterpart, the length of the code grows significantly, and it is much less readable and less maintainable than the sequential version. Most importantly, the code produced using the message passing paradigm usually uses much more memory than the corresponding code produced using high level parallel languages since a lot of buffer space is needed in the message passing paradigm. For these reasons, it is widely agreed that a higher level programming paradigm is essential if parallel systems are to be widely adopted. Most schools teaching the course use low-level message passing standard such as MPI or PVM and have not adopted OpenMP yet . To catch up the trend in industries, we decide to teach shared-memory parallel programming model besides the message passing parallel programming model. This paper describes my experience in using OpenMP as well as MPI to teach a parallel programming course at Georgia State University.

## 2 About OpenMP

The rapid and widespread acceptance of shared-memory multiprocessor architectures has created a pressing demand for an efficient way to program these systems. At the same time, developers of technical and scientific applications in industry and in government laboratories find they need to parallelize huge volumes of code in a portable fashion.

The OpenMP Application Program Interface (API)  supports multi-platform shared-memory parallel programming in C/C++ and Fortran on all architectures, including Unix platforms and Windows NT platforms. Jointly defined by a group of major computer hardware and software vendors, OpenMP is a portable, scalable model that gives shared-memory parallel programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer. It consists of a set of compiler directives and library routines that extend FORTRAN, C, and C++ codes to express shared-memory parallelism.

OpenMP’s programming model uses fork-join parallelism: master thread spawns a team of threads as needed. Parallelism is added incrementally: i.e. the sequential program evolves into a parallel program. Hence, we do not have to parallelize the whole program at once. OpenMP is usually used to parallelize loops. A user finds his most time consuming loops in his code, and split them up between threads. In the following, we will give some simple examples to demonstrate the major features of OpenMP.

Below is a typical example of big loops in a sequential C code:

```
void main()
{
    double A[100000];
    fo(int i=0;i<100000;i++) {
     big_task(A[i]);
    }
}

```

In order to parallelize the above code in OpenMP, users just need to insert some OpenMP directives to tell the compiler how to parallelize the loop. A short hand notation that combines the Parallel and work-sharing construct is shown below:

```
void main()
{
       double Res[100000];
#pragma omp parallel for
       for(int i=0;i<100000;i++)
       {
           big_task(Res[i]);
       }
}

```

The OpenMP work-sharing for construct basically splits up loop iterations among the threads in a team to achieve parallel efficiency. By default, there is a barrier at the end of the “omp for”. We can use the “nowait” clause to turn off the barrier.

Of course, there are many different OpenMP constructs are available for us to choose. The major difficult job in parallelize a code using OpenMP is how to choose an OpenMP construct, and where to insert them in the sequential codes. Smart choice will generate efficient parallel codes, while a bad choice of OpenMP directives may even generate a parallel code with worse performance than its original sequential code due to communication overheads.

When parallelize a loop in OpenMP, we may also use the schedule clause to perform different scheduling policies to effect how loop iterations are mapped onto threads. There are four scheduling policies available in OpenMP. The static scheduling method deal-out blocks of iterations of siz “chunk” to each thread. In the dynamic scheduling method, each thread grabs “chunk” iterations off a queue until all iterations have been handled. In the guided scheduling policy, threads dynamically grab blocks of iterations. The size of the block starts large and shrinks down to siz “chunk” as the calculation proceeds. Finally, in runtime scheduling method, Schedule and chunk size are taken from the OMP\_SCHEDULE environment variable and hence are determined at runtime.

The sections work-sharing construct gives a different structured block to each thread. This way, task parallelism can be implemented easily if each section has a task (procedure call). The following code shows that three tasks are parallelized using the OpenMP section work-sharing construct.

```
#pragma omp parallel
#pragma omp sections
{
        task1();
#pragma omp section
        task2();
#pragma omp section
        task3();
}

```

Another important clause is the reduction clause, that effects the way variables are shared. The format is reduction (op $`:`$ list), where op can be any general operations such as $`+`$, $`max`$, etc. The variables in each “list” must be shared in the enclosing parallel region. Local copies are reduced into a single global copy at the end of the construct. For example, here is an example for global sum and the final result is stored in the variable $`res`$.

```
#include <omp.h>
#define NUM_THREADS 2
void main ()
{       int i;
        double ZZ, func(), res=0.0;
        omp_set_num_threads(NUM_THREADS)
#pragma omp parallel for reduction(+:res) private(ZZ)
        for (i=0; i< 1000; i++)
        {
                ZZ = func(I);
                res = res + ZZ;
        }
}

```

Programming in a shared memory environment is generally easier than in a distributed memory environment and thus saves labor costs. However, programming using message passing in distributed memory environment usually produces more efficient parallel codes. This is much like the relationship between assembly languages and high level languages. Assembly codes run usually faster and are more compact than codes produced by high-level programming languages and are used often in real-time or embedded systems where both time and memory space are limited and labor costs are not the primary consideration. Besides producing efficient codes, assembly languages are also useful when students learn basic concepts about computer organization, arithmtic operation, machine languages, addressing, instruction cycles, etc. When we need to implement a large complicated program, high-level languages such as C, C++, or Java are more frequently used. Similarly, students can learn a lot of concepts such as scalability, broadcast, one-to-one communication, performance, communication overhead, speedup, etc, through low-level languages such as MPI or PVM. These concepts are hard to obtain through high-level parallel programming languages due to the fact that many details are hidden in the language constructs. However, students can implement a relatively large parallel program using high-level parallel language such as OpenMP or HPF easily within a short period of time. We believe that the future of high performance computing heavily depends on high level parallel programming languages such as OpenMP due to the increasingly high labor costs and the scarcity of good parallel programmers. High level parallel programming languages are one way to make parallel computer systems popular and available to non-computer scientists and engineers. Hence, teaching students how to use high level parallel programming languages as well as low level message passing paradigm is an important task for teaching parallel programming.

## 3 Why OpenMP and MPI

There are currently four major standards for programming parallel systems that were developed in open forums: High Performance Fortran (HPF) , OpenMP , PVM  and MPI .

HPF relies on advanced compiler technology to expedite the development of data-parallel programs . Thus, although it is based on Fortran, HPF is a new language, and hence requires the construction of new compilers. As a consequence each implementation of HPF is, to a great extent, hardware specific, and until recently there were very few complete HPF implementations. Furthermore most of the current implementations are proprietary and quite expensive. HPF has been written for the express purpose of writing data-parallel programs, and, as a consequence it is not well-suited for dealing with irregular data-structures or control-parallel programs.

The Parallel Virtual Machine (PVM) system uses the message-passing model to allow programmers to exploit distributed computing across a wide variety of computer types, including multiprocessor systems . A key concept in PVM is that it makes a collection of computers appear as one large virtual machine, hence its name. The PVM computing model is simple yet very general, and accommodates a wide variety of application program structures. The programming interface is deliberately straightforward, thus permitting simple program structures to be implemented in an intuitive manner. The user writes his application as a collection of cooperating tasks. Tasks access PVM resources through a library of standard interface routines. These routines allow the initiation and termination of tasks across the network as well as communication and synchronization between tasks. The PVM message-passing primitives are oriented towards heterogeneous operation, involving strongly typed constructs for buffering and transmission. Communication constructs include those for sending and receiving data structures as well as high-level primitives such as broadcast, barrier synchronization, and global sum.

MPI specifies a library of extensions to C and Fortran that can be used to write message passing programs . So an implementation of MPI can make use of existing compilers, and it is possible to develop more-or-less portable MPI libraries. Thus, unlike HPF, it is relatively easy to find an MPI library that will run on existing hardware. All of these implementations can be freely downloaded from the internet. Message passing is a completely general method for parallel programming. Indeed, the generality and ready availability of MPI have made it one of the most widely used systems for parallel programming. Compared with PVM library, MPI has become more popular recently.

Ideally, a parallel computing class would introduce students to both shared memory and distributed memory programming models. However, it is a truism that learning to program parallel systems is extremely difficult, and we believe that attempting to learn two essentially different methodologies in one semester or one quarter will, especially for the weaker students, make it virtually impossible to learn either. Thus in view of the difficulties involved in obtaining an HPF compiler and the generality of MPI, we have chosen to use MPI.

OpenMP has emerged as the standard for shared memory parallel programming. For the first time, it is possible to write parallel programs which are portable across the majority of shared memory parallel computers. OpenMP is a portable, scalable model that gives shared-memory parallel programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer.

The most important reason for us to adopt OpenMP in a parallel programming class is that students can parallelize some realistic code (not toy problems) within a short period of time due the programming ease it possesses. Students can also experiment with different scheduling schemes such as static or dynamic loop scheduling policies within a short period of time, which would be impossible otherwise using MPI.

Using OpenMP also has the advantage that task parallelism can be easily implemented by just inserting several OpenMP directives. By combining loop parallelism and task parallelism, better performance and higher scalability can be achieved. On the otehr hand, task parallelism is difficult to implement using MPI or HPF.

Another reason that we selected OpenMP in our class is that we have an SGI Origin 2000 shared memory multiprocessor system in our department. A shared memory programming model will fit in well.

Besides the above reasons, OpenMP has the following benefits for parallel programming compared with message passing models such as MPI:

a) A user just needs to add some directives into the sequential code to instruct the compiler how to parallelize the code. Hence, it has unprecedented programming ease, making threading faster and more cost-effective than ever before.

b) The directives are treated as comments when running a single processor. Hence, a single-source solution can be used for both serial and threaded applications, lowering code maintenance costs.

c) It is portable parallelism across Windows NT and Unix platforms.

d) The correctness of the results generated using OpenMP can be verified easily, to dramatically lower development and debugging costs.

Hence, our strategy is to teach students the basic concepts in parallel programming such as scalability, broadcast, one-to-one communication, performance, communication oevrhead, speedup, etc, through a low-level parallel programming language, and teach other concepts such as various scheduling policies and task parallelism through a high-level parallel programming language. Since MPI and OpenMP are the most widely used languages in the two categories, we select them to teach parallel programming.

## 4 Some Pitfalls with OpenMP

Because OpenMP is a high level parallel language, many details are hidden from a programmer. The good thing is that students can learn quickly and start to program immediately after learning some techniques. The pittfall is that students cannot clearly see the communications involved in a parallel program. Our approach to overcome this problem is to supplement OpenMP projects with some simple MPI programs. Students first learn the basics of parallel programs in a distributed memory environment. They start to parallelize a sequential code using simple MPI constructs such as MPI\_Bcast, MPI\_Reduce, MPI\_Send, and MPI\_Recv. Through several small projects, they learn the concepts of one-to-one communication, multicast, broadcast, reduction, synchronization, and concurrency. Later, when they use OpenMP to parallelize a program, they already have a deep understanding of communication structure, communication overhead, scalability and performance issues.

The second shortcoming with OpenMP is that it does not provide memory allocation schemes for arrays and other data structures since OpenMP is designed for shared memory machines. Again, this relieves the students from complication memory allocation decisions and they can concentrate on loop and task parallelism. This is good for the ease of programming, but students do not know the details of array allocation schemes such as BLOCK or CYCLIC schemes commonly used in distributed memory environments. Since the memory on the SGI Origin 2000 is not physically shared, SGI provides data distribution directives to allow users to specify how data is placed on processors. If no data distribution directives are used, then data are automatically distributed via the “first touch” mechanism  which places the data on the processor where it is first used. Because different allocation schemes may affect the performance of a program greatly, SGI data distribution directives are required in the final project to show the performance improvement. For example, the following data distribution directive distribute the 4D array H on dimension 2:

```
!$sgi distribute_reshape H(*,BLOCK,*,*)

```

Students are required to try several data distribution schemes, to observe the running times and to comment on the timing results as described below. In this way, the relationship between memory allocation schemes and performance is demonstrated.

Due to these pitfalls with OpenMP, students would not learn all the concepts and the whole picture in parallel programming using OpenMP alone. Our strategy is to supplement OpenMP with explanation on several typical MPI codes and small projects using MPI standard. Then, students experiment with various scheduling policies and complicated parallelization methods in OpenMP. In this way, students experience various parallel schemes and techniques in a short period of time. This would be very hard to achieve if only MPI or PVM programming model is used in teaching parallel programming due to the facts that it is very time consuming to implement in MPI or PVM and that students cannot parallelize a large code in MPI or PVM within a short period of time. The following section will detail the strategy of using both OpenMP and MPI adopted in my class.

## 5 Using MPI and OpenMP in Projects

The parallel programming class at GSU is a semester-long class for upper-level undergraduates and beginning graduate students. In it we used tutorials on MPI and OpenMP from Ohio Supercomputing Center as supplements to a parallel algorithms textbook . The code that we present in the lectures uses both C and Fortran.

The course begins with an overview of parallel computing and continues with a brief introduction to parallel computing models such as various PRAMs, shared memory models and distributed memory models. The concepts of data parallelism and pipelining are also introduced at that time. The next block of lectures forms a transition into a more or less standard parallel algorithms course. We first discuss serial and parallel versions of a very simple computation – e.g., prefix sums and prime finding. In the course of analyzing the performance of these algorithms, we develop the concepts of speedup, scalability and efficiency. The deterioration of the performance of the parallel algorithm as the number of processes is increased leads naturally into a discussion of Amdahl’s Law and scalability.

The course work consists of two tests, a final exam, five programming projects and a research paper. Since the course’s emphasis is on parallel programming, projects are an important part of the course. The purpose of the first project is simply to acquaint students with the system and programming environment of the Origin 2000. In it, they write a simple addition code, and measure the parallel times using different number of processors.

In the second project, the students implement an MPI code to calculate $`\pi `$ using Simpson’s Rule instead of the rectangle rule discussed in class, where students are exposed to various MPI communication functions. For timing measurements and precision, they need to test the code using several different numbers of subintervals to see the effect on the precision of results and different number of processors on the execution times.

In the third project, the students implement parallel game of life. Through the assignment, students learn various domain decomposition strategies. All the above projects are implemented in MPI.

Now students already understand the communication mechanism of parallel computing systems, and communication overhaed within a parallel code, it is time to introduce OpenMP. After briefly discussing how to use OpenMP and showing them several OpenMP examples, students are asked in the fourth project to initialize a huge array $`A`$ so that each element has its index as its value. Then they are required to create a real array $`B`$ which will contain the running average of array $`A`$. They need to parallelize the loops with all four scheduling schemes available in OpenMP (static, dynamic, guided, and runtime) and measure the running times with different scheduling policies and different chunk sizes. They are also required to write their observations on the timings using the four different scheduling policies and to explain why the performance is different for using different scheduling policies and different chunk sizes.

In the fifth project, students learn how to parallel a real research Fortran code in OpenMP. The project contains several parts. They first parallelize the major loops in the code in OpenMP. Then, they parallelize the code using both loop and task parallelism in OpenMP. Now, they have obtained the best scheduling policy, best chunk size for the policy, and both loop and task parallelism in the above two steps. But array mapping is done automatically by the OpenMP compiler. In the final step, they need to distribute the arrays manually using SGI array distribution directives since array distribution directives are not available in OpenMP. The purpose is for students to understand the effect of array distribution on the running performance. They are also required to write a short report to summarize the results obtained. Through these steps, students learned how to parallelize a real code in a step-by-step fashion.

Students are also required to write a research paper or a survey paper on a chosen topic in parallel processing. The purpose is for the students to apply the knowledge learned in the course to some problems. Some students implemented some algorithms using MPI and/or OpenMP using various strategies and compared the performance their implementations with the results published in the literature. At the end of the term, students need to present their findings besides submitting a paper.

The outcome of the course is very good. Most students feel that they learned a lot in the course based on student evaluations and comments from them on the course. Some of the students already applied their knowledge learned in the course to our research projects supported by NSF and Air Force. One student implemented a parallel program for Cholesky factorization using both MPI and OpenMP and did a lot of testing using various scheduling and partition strategies. He also did a comprehensive compariosn among the different implementations, and wrote an excellent research paper at the end of the course. The paper is being revised and potentially could be published in a conference. This would have been impossible if only MPI had been taught in the course.

## 6 Conclusion

As OpenMP becomes more popular for parallel programming and has many advantages over message passing programming models, it is important to introduce OpenMP in a parallel programming course. However, OpenMP also has some shortcomings for teaching parallel programming concepts. Our strategy is to use MPI to convey the basic concepts of parallel programming and to use OpenMP to tackle more complicated problems such as various scheduling policies and combined loop and task parallelism. It seems the strategy is well received by my students.


text:
# Untitled Document

Effects of temperature and sulphur on the composition profile of Pt-Rh nanocatalysts : A comparative study.

Abir De Sarkar and Badal C. Khanra

Condensed Matter Physics Group, Saha Institute of Nuclear Physics,

1/AF, Bidhannagar, Calcutta - 700064, India

Abstract

Monte-Carlo simulation technique has been used to investigate the effect of temperature and adsorbed gases on the composition profile of unsupported Pt-Rh nanocatalysts. For a 2406 atom fcc cubo-octahedral Pt50Rh50 nanocatalyst the shell-wise composition for all the eight shells has been simulated. For the temperatures 700 K, 1000 K and 1300 K, the top shell of clean Pt-Rh nanocatalysts is found to be mildly Pt-enriched, while the second shell is Pt-depleted. The Pt concentration of the top shell shows a maximum at T = 1000 K. In presence of a quarter monolayer of adsorbed oxygen the top shell shows Rh enrichment, while all the other shells show Pt-enrichment. This is true for all the three temperatures for which the composition profiles have been studied.

PACS: 61.46.+W, 61.66Dk,68.10. Jy, 68.35. Md

Keywords: Nanocatalysts, segregation, Monte-Carlo simulation, adsorption

$``$ Corresponding Author
FAX (91) (33) 337 4637
Email: ¡badal@cmp.saha.ernet.in¿

1. Introduction

The ceria-supported Pt-Rh bimetallic catalysts have been found to be very effective three-way catalysts for simultaneous elimination of the CO , NO and the hydrocarbons from automobile exhaust gases \[1-3\]. These catalysts are increasingly used globally in the catalytic converters of automobiles. It is important, therefore, to have a thorough understanding of the structural, electronic and catalytic properties of these catalysts. In this work , we present the results of our theoretical investigations on the composition profile of unsupported Pt-Rh bimetallic nanostructures as a function of temperature and adsorbates.

The structural and catalytic properties of the Pt-Rh alloy surfaces have earlier been exhaustively studied by several groups \[4-11\]. Van Delft et al.  used AES to investigate the Pt62Rh38 and Pt10Rh90 alloy systems. They found a surface enrichment with Pt for both the systems. When studied as a function of temperature this surface enrichment showed a maximum at about 1000 K for both the systems. This phenomenon was explained in terms of a vibration entropy contribution to the enthalpy. Tsong et al.  made a layer-by-layer analysis of a Pt-Rh alloy tip at 1000 K to show that the topmost layer is Pt-enriched and the second layer is Pt-depleted. The distribution of Pt and Rh atoms depend on the annealing temperature. Hirano et al.  , on the other hand, showed that the presence of adsorbates like oxygen and/or nitric oxide has a more pronounced effect on the chemical restructuring process of the Pt-Rh surface layers than the annealing temperature. While there have been a large number of theoretical studies on this segregation phenomenon in clean and gas-covered alloy surfaces \[4-7\], the number of segregation studies for supported particles are comparatively few. Some theoretical investigations for Pt-Rh particles have been made by Strohl and King , Schoeb et al.  and Yang et al . These works are based either on rigid-lattice Monte-Carlo (MC) simulations or on molecular dynamics / Monte-Carlo-correlated effective medium theory, where the interaction energies were generated from a simplified version of the non-selfconsistent electron-density-functional correlated effective medium (CEM) theory . For the fcc cubo-octahedral particles the atomic distribution at the corner, edge and fcc(100) and (111)-like faces were obtained as a function of the particle size and composition. A shell-by-shell composition profile of the particles were not, however, studied in these works. It is the main purpose of the present work to investigate the shell-wise composition of Pt-Rh nanoparticles as a function of temperature and adsorbate coverage. For the 2406 fcc cubo-octahedral Pt-Rh nanoparticles a Monte-Carlo simulation has been carried out to analyse the atomic distribution in top few layers . We show that the presence of adsorbate like oxygen drastically changes the composition profile, while the effect of temperature from 700K-1300 K on the composition profile is relatively much small. These studies are useful in understanding the structure and catalytic properties of ceria-supported Pt-Rh catalysts used in the catalytic converter . The plan of the paper is as follows. In section 2, the theoretical model developed earlier and used in the present work is briefly outlined. The results for clean and oxygen-adsorbed Pt-Rh nanoparticles are presented in section 3. The conclusions are drawn in section 4.

2. Theoretical model

The theoretical model used in this work is the MC simulation technique employed elsewhere in connection with surface segregation in presence and in absence of adsorbed species\[12-16\]. One determines the pair-bond energy between two nearest neighbour atoms Eij in the form

$$E_{\mathrm{ij}}=w_{\mathrm{ij}}/Z+E_\mathrm{c}^\mathrm{i}(n)/n+E_\mathrm{c}^\mathrm{j}(m)/m$$
(1)
where the indices i and j are the component metals A or B of the bimetallic system AB ; and wij is the interchange energy for two dissimilar atoms. wij = 0 if i = j and this interchange energy is related to the excess heat of mixing. Z is the bulk coordination number. E$`{}_{}{}^{i}{}_{c}{}^{}`$ (n) is the partial bond energy of the i-atom with n nearest neighbours etc. Usually, the coordination-dependent partial bond energy , Eci (n) ( for n = 2 - 12), is calculated from an empirical formula like

$$E_\mathrm{c}^\mathrm{i}(n)=a^\mathrm{i}+b^\mathrm{i}n+c^\mathrm{i}n^2$$
(2)
where ai, bi and ci are adjustable constants that can be derived from experimental data of dimer energy , surface energy and the cohesive energy of a metal corresponding to n=2, 8 and 12 respectively. Once the pair binding energy Eij is evaluated it is the usual MC procedure to compute the configuration energy for a particular distribution of A and B atoms in the nanoparticle. And from various such distributions an equilibrium distribution may be found giving the shell-wise occupation of sites by A or B atoms. In presence of adsorbates, there are additional energy terms to describe the chemisorptive bond and the concomitant metal-metal pair-bond energy variations. King and Donnelly  showed that since in Monte-Carlo simulations only the differences in energies are calculated, it is sufficient to add the difference in chemisorption energy of the adsorbate on the two metals to the configuration energy. This has been done in this work to study the role of adsorbed oxygen on the composition profile.

3. Results and Discussions

We are interested in the composition profile of the outer shells of the Pt-Rh nanoparticles since it is only the outer shells which are important in catalysis and can be influenced by adsorbed atoms. For convenience, we avoid the usual description of shell structure where the shells are constructed by atoms equidistant from the centre. As may be found from the work of Yang and DePristo  that to describe a 200-atom fcc cubo-octahedral particle one needs 11 shells. This concept may be very useful for describing the stability and morphological structure of a nanoparticle. However, for a large fcc cubo-octahedron particle of 2406 atoms as considered in this work this description would require a large number of shells which is very difficult to handle. In our treatment , the outermost shell (we also call it ‘top shell’) comprises all the atoms at the corner sites, bridge sites, fcc(100) and fcc(111)-type faces. The total number of such atoms is 752. If we peel off these atoms from the outermost shell, the second shell would be exposed to the adsorbed gases. The number of atoms in the second shell is 582. In this way, we may have just eight shells with total number of atoms in the shells ( counting from the outermost shell inward) as 752, 582, 432, 302, 192, 102, 38 and 6 respectively. The number of Pt and Rh atoms are counted in each shell and the fraction of these atoms in the shells are calculated. In this work we have calculated the fraction of Pt and Rh atoms for a bulk Pt50Rh50 particle.

The values of the parameters used for the present MC simulation are the following:

Pt: a = -0.4287398, b = -0.0474969, c = 0.0035483 , Ead(O) = 85 kcals/mole

Rh: a = -0.4744544, b = - .0341727, c = 0.0028138 , Ead(O) = 102 kcals/mole

and wij /Z = -0.00691 eV. Ead(O) is the chemisorption energy of oxygen atom on the metal.

We have calculated the composition profile for T = 700 K, 1000 K and 1300 K. The studies at T = 700 K is of particular importance since the exhaust temperature at the three-way catalyst is of this order. To study the effect of adsorbed gases we have considered one coverage ( = 0.25 ) of adsorbed oxygen. This is because it is the presence or absence of oxygen that controls the CO oxidation and NO reduction in three-way catalysts. The calculation , however, can easily be repeated for other coverages and other adsorbed gases . The present work attempts to study the qualitative change of composition profile as a function of temperature and adsorbate coverage.

Figure 1 shows the % of Pt atoms in top four shells. The top shell ( shell number 1) corresponds to the surface layer and shows Pt-enrichment for all the three temperatures; while the second and third shell shows Pt-depletion for the three temperatures. The no segregation line is represented by the dots. The behaviour from shell number 4 to higher ( moving towards the core of the particle ) is divergent. However, for surface and catalytic properties the top 2-3 shells are of real interest since they constitute the surface layers . Besides, the top shell for a 2406-atom particle represents 31% of total atoms, sometimes known as dispersion; while the top 2 , top 3 and top 4 shells represent 55% , 73% and 86% of total atoms for this particle respectively. If we compute the % of Pt atoms averaged over top 2, top 3 and top 4 shells, the results would be as shown in Figure 2. The results are computed for all the three temperatures. The results averaged over all the eight shells would ,of course, be the bulk Pt concentration which is 50%. This is why all the curves meet at shell number 8. It may be noted that for T = 700 K the top shell is Pt-enriched; but the averages over top 2, top 3 and top 4 shells show Pt-depletion. For T = 1000 K and 1300 K, however, the averages over top 2, top 3 and top 4 shells show Pt-enrichment. This signifies that the properties, that depend on the composition of the top shell only, would not change with temperature, since the shell is Pt-enriched. However, the properties that depend on the average composition of top 2 , top 4 or top 4 shells will change with temperature. In Figure 3 we plot the same shell-averaged Pt concentration as a function of temperature. In addition to the features described above for Figure 2, an important feature becomes obvious in figure 3. It is that the Pt-enrichment shows a maximum at T = 1000 K. This result agrees very well with the experimental findings of Van delft et al.  for the polycrystalline alloy surface. The authors  explained this behaviour with a surface segregation model containing both enthalpy and vibrational entropy contribution. It is likely that for the present system of nano-sized Pt-Rh particles also the entropy contribution may be responsible for the temperature dependence of surface segregation. In Figure 4 we plot the % of Pt atoms in presence of 0.25 monolayer of adsorbed oxygen and compare them with the results for clean system, shown already in Figure 1. It may be noticed that the presence of 0.25 monolayer of oxygen has a very strong effect on the composition of the top shell as well as on other shells. Because of higher binding energy of oxygen on Rh compared to that on Pt the Rh atoms are pulled to the top shell at all the three temperatures. This segregation is so strong that the rest of the shells of the particle become Pt-enriched. On comparing the effect of temperature and adsorbates on the shell composition it may be noted from Figure 4 that the effect of temperature on the composition profile is mild. This is obvious from the spreadth of the composition for three temperatures in both the clean and adsorbed cases. However, the large separation of the two sets of curves ( each set consisting of the results for three temperature), one for the clean case and the other for the oxygen-adsorbed case, signifies that the effect of adsorbates is much stronger on the composition. We believe, these results can be exploited in the three-way catalyst where Rh acts as the main component in reducing NO. Furthermore, it may be mentioned that the present study considers one bulk composition and one coverage of one adsorbed species. This may be repeated for other compositions, adsorbates and coverages as the situation demands.

4. Conclusions

A Monte-Carlo procedure has been utilised to compute the atomic composition of a Pt-Rh nanoparticle in the form of shells gradually peeled off from the outer layer. The composition profile correctly predicts Pt segregation in the top layer ; but the variation of the composition of the outer shells with temperature is small. In contrast, the variation of the composition of the shells with presence of adsorbed oxygen is very large.

References

 K. C. Taylor, In Automotive Catalytic Converters, Springer, Berlin(1984).

 K. Taschner, In Catalysis and Automotive Pollution Control II, Ed. A. Crucq, Elsevier, Amsterdam,(1991),p-17.

 C. Howitt, V. Pitchon, F. Garin and G. Maire, In Catalysis and Automotive Pollution Control III, Eds. A. Frennet, and J. M. Bastin, Elsevier, Amsterdam (1995), p-149.

 F. C. M. J. M. Van Delft, Surf. Sci. 189/190 (1987) 1129.

 T. T. Tsong, D. M. Ren and M. Ahmad, Phys. Rev. B38 (1988)7428.

 H. Hirano, T. Yamada, K. Tanaka, J. Sierra and B. E. Nieuwenhuys, Vacuum 41(1990) 134; H Hirano, T. Yamada, K. Tanaka, J. Sierra and E. Nieuwenhuys, Surf. Sci. 222(1989)L804; H Hirano, T. Yamada, K. Tanaka, J. Sierra and B. E. Nieuwenhuys, Surf. Sci. 226(1990)1.

 F. C. M. J. M. Van Delft, B. E. Nieuwenhuys, J. Sierra and R. M. Wolf, ISIJ International, 29(1989)550.

 J. K. Strohl and T. S. King, J. Catal. 116 (1989)540, ibid. 118(1989)53.

 A. M. Schoeb, T. H. Raeker, L. Yang, X. Wu, T. S. King and A. E. DePristo, Surf. Sci. Lett 278(1992) L125.

 L. Yang and A. E. DePristo, J. Catal. 148 (1994)575.

 M. S. Stave, D. E. Sanders, , T. J. Raeker and A. E. DePristo J. Phys. Chem. 93(1989) 1556.

 T. S. King and R. G. Donnely, Surf. Sci.141(1984)417.

 B. C. Khanra and M. Menon, Chem. Phys. Lett. 305(1999)89.

 B. C. Khanra and M. Menon, Physica B 291(2000)368.

 A. De Sarkar, M. Menon and B. C. Khanra, Appl. Surf. Sci. (In press)

Figure Caption

Fig. 1. MC-simulated % of Pt atoms in different shells of a 2406-atom Pt50Rh50 nanoparticle for different temperatures .

Fig. 2. MC-simulated average % of Pt atoms in top, top 2, top 3 and top 4 shells of a 2406-atom Pt50Rh50 nanoparticle for different temperatures.

Fig.3. MC-simulated average % of Pt atoms in top, top 2, top 3 and top 4 shells of a 2406-atom Pt50Rh50 nanoparticle plotted as a function of temperature to demonstrate the existence of a maximum at T = 1000 K.

Fig. 4. MC-simulated % of Pt atoms in different shells of a clean and oxygen-adsorbed 2406-atom Pt50Rh50 nanoparticle .


text:
# Significant discrepancies between stellar evolution models and solar-type eclipsing and visual binaries ?

## 1. Introduction to the problem

The study of stars with masses larger than $``$0.6 M bypasses difficulties in the treatment of the equation of state and the atmosphere. On the other hand, stars with masses greater than about 1.1 M have a permanent convective core, introducing an additional parameter, the amount of overshooting. Therefore, we expect current stellar evolution models to be able to match the basic properties of stars in the 0.7-1.1 M mass range. In particular, some detached binaries provide very accurate stellar data so they are ideal candidates to critically test sets of theoretical models. Nevertheless, as pointed out by Popper (1997), a serious dilemma appears to be present in the comparison of fundamental stellar properties derived from observations and the predictions of stellar models. In the next sections we review stellar objects (EBs in the field and in the Hyades and one visual binary) suggesting that current stellar models present some problems around the mass of the Sun.

## 2. Eclipsing binaries in the field

We consider the following detached eclipsing binaries (DEBs): RT And, HS Aur, CG Cyg and FL Lyr. We obtain bad fits by fitting both components simultaneously in the HR diagram with Padova group (Fagotto et al. 1994) or Geneva group (Mowlavi et al. 1998) models. Either these stellar models are unreliable in this part of the HRD, or the Teffs of (at least) the secondaries need revision. As shown by Pols et al. (1997), the same difficulty appears with the Cambridge group models by fitting simultaneously the effective temperature (Teff), mass ($`M`$) and radius ($`R`$). Clausen et al. (1999) recently reviewed this dilemma with other sets of theoretical models, getting bad fits as well.
Could the measurements be responsible of this problem ? The relative error on the individual Teffs of the sample is always small ($`<`$3.5%). However, while the mass and radius of each component of DEBs can be accurately measured (1-2%), the use of Teff (and so luminosity) is not as reliable because derived indirectly (from various photometric or spectroscopic indicators) and thus may explain part of the problem. Lastennet et al. (1999a), Ribas et al. (2000), and Lastennet, Cuisinier & Lejeune (these proceedings) attempted to carefully re-derive reliable EBs Teffs, but unfortunately none of these works study the stars in question because individual $`uvby`$ photometry would be necessary. Mass transfer should not be an explanation because none of these stars overflows its Roche lobe (Lastennet 1998): HS Aur A: $``$11%, B: $``$10%; FL Lyr A: $``$35%, B: $``$29%; CG Cyg A: $``$61%, B: $``$60%; RT And A: $``$77%, B: $``$64%. Nevertheless, for the system RT And, the face-to-face position of the spots on the surface of both components may indicate the possibility of a mass transfer from the primary to the secondary component through a magnetic bridge connecting both active regions (Pribulla et al. 2000).

## 3. Eclipsing binaries in open clusters

As discussed for instance by Lastennet et al. (2000), DEBs members of a star cluster provide stringent constraints on stellar evolution models when the metallicity of the cluster is known. The eclipsing binary V818 Tauri (a member of the Hyades) contains 2 stars in the 0.7-1.1 M mass range (1.072$`+`$0.769 M, Peterson & Solensky 1988). Once again, a similar analysis for this binary (Lastennet et al. 1999b) found no Padova models fitting simultaneously $`M`$ and $`R`$ (thus, without using any information on Teff) for any age or metallicity.

## 4. Visual binaries

Such a problem was also detected in this mass range by Fernandes et al. (1998) for 85 Peg (0.91$`\pm `$0.11 M$`+`$0.73$`\pm `$0.13 M), a nearby visual binary star ($``$12.4 pc). They found no solution satisfying the constraint of the luminosity ($`L`$) and Teff for both stars and corresponding to the observed metallicity and sum of the masses. 85 Peg A and B appeared to be too cold and/or over-luminous with respect to the ZAMS. Only models with extremely low helium ($`Y`$$`<`$0.20) and high age (20 Gyr) could fit the HR diagram position of 85 Peg A, which seems definitively unrealistic since the primordial helium is estimated to be $`Y`$$`=`$0.232$`\pm `$0.003 (Olive & Steigman 1995) and the age of the Universe to be between 10-20 Gyr. They succeeded to fit the 85 Peg A position by decreasing $`\alpha `$MLT to about 1.0 but a similar change of $`\alpha `$MLT didn’t fit the 85 Peg B position. A more recent study (Lebreton et al. 1999) shows that including the diffusion, the contribution of the $`\alpha `$-elements, and non LTE-effects in low metallicity models help solving the above discrepancy, but there is still a problem to match the mass of the secondary. A new study of 85 Peg is underway (Fernandes et al., in prep.) but the influence of rotation can already be excluded because vsin$`i`$ is very low (vsin$`i`$$`<`$5 km.s-1, according to the catalog of Glebocki & Stawikowski, 2000).

## 5. Future theoretical projects with CESAM

The systematic discrepancy presented previously is not observed in CD Tau C, a solar mass companion of the triple system CD Tau: Ribas et al. (1999) obtained a perfect fit of the 3 components with a single isochrone. Therefore, except CD Tau C (whose mass still needs an accurate measure), the other examples show that there is still great problems for the stellar evolution theory to predict the properties of solar-type stars. However, this is of first importance for stellar theory to match at least the best known objects (the Sun and non-interacting binary systems) before any attempt to derive information for star clusters or stellar populations in galaxies. To tackle this problem, the CESAM code (Morel 1997) should be very useful to explore the influence of each physical parameter. CESAM performs calculations of 1D quasi-static stellar evolution including diffusion and mass-loss and computes the evolution of stars from the pre-main sequence (PMS) to the beginning of the red giant branch.

As suggested by Clausen et al. (1999), the problem briefly presented in the previous sections may be removed (or at least diminished) if a significantly lower $`\alpha _{MLT}`$ is adopted for the less massive secondary components. A recent study on V818 Tau (Lebreton et al. 2001) seem to support this idea and similar tests on the EBs of §2 are in progress (Lastennet & Fernandes). We suggest a detailed study of each system to check if there is a solution for a set of ($`\alpha _{MLT}`$, $`Y`$, $`Z`$, age). Even if the effect of stellar rotation is usually negligible for stars less massive than $``$1.4 M, an even slightly effect on Teff and $`L`$ may be relevant for some of these stars (e.g. vsin$`i`$ $``$70 km.s-1 for both components of CG Cyg). Another explanation may be that some of these stars are still in the PMS phase, and this is another advantage to use the CESAM code which includes this phase.

## 6. Future constraints from new observational campaigns and GAIA

Of course, the number of relevant systems is still very small to give a definitive conclusion. A photometric and spectroscopic observational campaign of about 50 newly discovered Hipparcos EBs at OHP (France), Kryonerion (Greece) and Cracow (Poland) would increase the number of objects (Kurpinska-Winiarska & Oblak 2000), as well as the dedicated observational program of late F, G and K type stars at the Danish 50 cm SAT (La Silla Obs., Chile) which already provided new candidates (Clausen, Helt & Olsen 1999). The GAIA satellite would also increase the number of stars with individual masses. Halbwachs & Arenou (1999) estimated that the individual masses of 79 double-lined spectroscopic binaries (SB2s) - which are not eclipsing binaries \- in the 8th catalogue of orbital elements of SB systems (Batten et al. 1989) would be derived from the GAIA astrometric observations. We expect some of them ($``$ 10 according to Tab. 1 of Halbwachs & Arenou) to belong to the mass range discussed in the present work.

## 7. Conclusion

We review solar-type stars showing a clear discrepancy between their fundamental properties and stellar model predictions. This indicates problems in current stellar evolutionary models because a revision of their Teff would not solve the disagreement regarding the masses and radii (see Tab. 7 of Popper 1997, or Fig. 4 in Lastennet et al. 1999b). These stars belong to binary systems without interaction so representative of single stars, and it is of first importance for stellar theory to match at least the best known objects (the Sun and non-interacting binary systems). In an attempt to solve this problem, we suggest some theoretical explorations, in particular a detailed study of stellar rotation and PMS phases. We also present some projects which should help to increase the limited number of accurate fundamental parameters of detached EBs.

### Acknowledgments.

E.L. thanks J.-L. Halbwachs for useful comments about SB2s and GAIA.

## References

Clausen J.V., et al., 1999, ASP Conf. Series 173, 265

Clausen J.V., Helt B.E., Olsen E.H., 1999, ASP Conf. Series 173, 321

Fagotto F., Bressan A., Bertelli G., Chiosi C., 1994c, A&AS, 105, 39

Fernandes J., Lebreton Y., Baglin A., Morel P., 1998, A&A, 338, 455

Glebocki R., Stawikowski A., 2000, Acta Astronomica, 50, 509.

Halbwachs J.L., Arenou F., 1999, Baltic Astronomy 8, 301

Kurpinska M., Oblak E., 2000, IAU Symp. 200, eds. B. Reipurth & H. Zinnecker, p.141

Lastennet E., 1998, Ph-D thesis, Univ. L. Pasteur, Obs. de Strasbourg, France

Lastennet E., Lejeune Th., Westera P., Buser R., 1999a, A&A, 341, 857

Lastennet E., Valls-Gabaud D., Oblak E., 2000, IAU Symp. 200, eds. B. Reipurth & H. Zinnecker, p.164

Lastennet E., Valls-Gabaud D., Lejeune Th., Oblak E., 1999b, A&A, 349, 485

Lebreton Y., et al., 1999, A&A, 350, 587

Lebreton Y., Fernandes J., Lejeune Th., 2001, A&A accepted (astro-ph/0105497)

Morel P., 1997, A&AS, 124, 597

Mowlavi N. et al., 1998, A&AS, 128, 471

Olive K.A., Steigman G., 1995, ApJS, 97, 49

Peterson D.M., Solensky R., 1988, ApJ, 333, 256

Pols O.R. et al., 1997, MNRAS, 289, 869

Popper D.M., 1997, AJ, 114, 1195

Pribulla T. et al., 2000, A&A, 362, 169

Ribas I. et al., 1999, MNRAS, 309, 199

Ribas I., Jordi C., Torra J., Giménez A., 2000, MNRAS, 313, 99


text:
# Test of the Polyakov Loop Model

## Abstract

We discuss the two point functions for the real and imaginary parts of the Polyakov loop in a pure $`SU(3)`$ gauge theory. The behavior of these correlation functions in the Polyakov Loop Model is markedly different from that in perturbation theory.

Consider the behavior of an $`SU(3)`$ gauge theory without dynamical quarks. The usual quantity measured is the pressure, as a function of the temperature. While important, and indeed the only thing which one needs for thermodynamics, there are many other things to measure, such as the correlation functions of gauge-invariant operators.

In this note we discuss what certain correlation functions may tell us about the behavior of the deconfined phase. We work within the context of the Polyakov Loop Model . For reasons which will become clear later, however, it is probably imperative to think of how to parametrize these correlation functions in a manner independent of any theoretical prejudice.

At a nonzero temperature $`T`$, a fundamental quantity is the thermal Wilson Line,

$$𝐋(\stackrel{}{x})=𝒫\mathrm{exp}\left(ig_0^{1/T}A_0(\stackrel{}{x},\tau )𝑑\tau \right).$$
(1)
This transforms as an adjoint field under the local $`SU(3)/Z(3)`$ gauge symmetry, and as a field with charge one under the global $`Z(3)`$ symmetry. To obtain a gauge invariant operator, the simplest thing to do is to take the trace, forming the Polyakov loop,

$$\mathrm{}_1=\frac{1}{3}\mathrm{tr}\left(𝐋\right).$$
(2)
This transforms under the global $`Z(3)`$ as a field with charge one. The expectation value of $`\mathrm{}_1`$ is only nonzero above $`T_c`$, which is the temperature for the deconfining phase transition.

In fact $`\mathrm{}_1`$ is only the first in an infinite series of gauge-invariant operators. For example, consider

$$\mathrm{}_2=\frac{1}{3}\mathrm{tr}\left(𝐋^2\right)\mathrm{}_1^2.$$
(3)
Under the global $`Z(3)`$ symmetry, this Polyakov loop has charge two. The charge one part of $`\mathrm{tr}(𝐋^2)`$, $`\mathrm{}_1^2`$, is subtracted off to obtain an independent field. In this note we concentrate only upon the charge one Polyakov loop, $`\mathrm{}\mathrm{}_1`$, and drop all Polyakov loops with other charges, such as $`\mathrm{}_2`$, the singlet field $`\mathrm{}_3\mathrm{tr}(𝐋^3)+\mathrm{}`$, etc.

We begin with a potential for the Polyakov loop, taking the simplest form consistent with the global $`Z(3)`$ symmetry:

$$𝒱(\mathrm{})=\frac{b_2}{2}|\mathrm{}|^2\frac{b_3}{3}\left(\mathrm{}^3+(\mathrm{}^{})^3\right)+\frac{1}{4}\left(|\mathrm{}|\right)^2$$
(4)
The coefficient of the quartic term is chosen to simplify further results. At the minimum of the potential, which we assume occurs for real $`\mathrm{}`$, $`𝒱/\mathrm{}=0`$,

$$\mathrm{}_0\mathrm{}=b_3+\sqrt{b_2+b_3^2}.$$
(5)
In the Polyakov Loop Model, the pressure is related to the potential as:

$$p(T)=𝒱(\mathrm{}_0)b_4T^4.$$
(6)
At high temperatures, $`b_2`$ is adjusted so that $`\mathrm{}_01`$; then $`b_4`$ is adjusted to give the proper value of the ideal gas term. Away from infinite temperature, in the spirit of mean field we take the quantities $`b_3`$ and $`b_4`$ to be approximately constant with temperature. Given the pressure, the dependence of $`b_2`$ upon the temperature is then fixed.

While $`\mathrm{}_0`$ is the standard variable measured on the lattice, this is the bare value. Single insertions of the Polyakov loop are regularized by introducing a renormalization constant; the natural condition to fix the value of that constant is to require that the renormalized Polyakov loop is unity at infinite temperature . If a lattice regulator is used instead of dimensional regularization, though, one has to deal with divergences $`g^2/(aT)`$, etc., which are most singular as the lattice spacing $`a0`$.

Thus at present, we cannot easily relate the one point function of the Polyakov loop, as measured on the lattice, to the pressure. However, we now show that for three colors, one can relate certain two point functions of the Polyakov loop, to the pressure, in an unambiguous fashion.

For $`SU(3)`$, the Polyakov loop is a complex number, with real, $`\mathrm{}_r=\mathrm{Re}\mathrm{}`$, and imaginary, $`\mathrm{}_i=\mathrm{Im}\mathrm{}`$, parts. By a global $`Z(3)`$ rotation, we can assume that the vacuum expectation value of $`\mathrm{}`$, $`\mathrm{}_0`$, is real. Computing second derivatives, the mass squared for the real part is:

$$m_r^2=\frac{^2𝒱}{\mathrm{}_r^2}=b_24b_3\mathrm{}_0+3\mathrm{}_0^2,$$
(7)
while that for the imaginary part is:

$$m_i^2=\frac{^2𝒱}{\mathrm{}_i^2}=b_2+4b_3\mathrm{}_0+\mathrm{}_0^2.$$
(8)
When $`b_30`$, the transition is necessarily of first order. The transition occurs when the nontrivial minimum is degenerate with the trivial minimum; i.e., when $`𝒱(\mathrm{}_0)=0`$. Putting in the expression for $`\mathrm{}_0`$, we find

$$b_2(T_c^+)=\frac{8}{9}b_3^2,\mathrm{}_0(T_c^+)=\frac{4}{3}b_3.$$
(9)
This is all trivial algebra, done in detail to avoid any possible confusion. The full effective lagrangian can then be computed. Besides the potential term, given above, there is also the kinetic term, with a nonstandard normalization:

$$𝒵_WT^2|\stackrel{}{}\mathrm{}|^2,𝒵_W=\frac{3}{g^2}\left(1.08\frac{g^2}{4\pi }+\mathrm{}\right).$$
(10)
The first term in $`𝒵_W`$ appears at the classical level, while the second arises from one loop corrections, as computed by Wirstam .

Over large distances, $`x\mathrm{}`$, the two point functions of the Polyakov loop are

$$\mathrm{}_r(x)\mathrm{}_r(0)\mathrm{}^2\frac{\mathrm{exp}(\stackrel{~}{m}_rx)}{x},$$
(11)
$$\mathrm{}_i(x)\mathrm{}_i(0)\frac{\mathrm{exp}(\stackrel{~}{m}_ix)}{x}.$$
(12)
The two fields, $`\mathrm{}_r`$ and $`\mathrm{}_i`$, don’t mix to the order at which we work. The masses which enter into the correlation functions are

$$\stackrel{~}{m}_{r,i}^2=\frac{b_4}{𝒵_W}m_{r,i}^2T^2.$$
(13)
For two colors, the Polyakov loop is real, and one can only measure one mass. Then, without knowing both the coupling constant and the wave function renormalization constant $`𝒵_W`$, there is no firm prediction.

This is not true for three colors. Then one can form the ratio of the masses for the real and imaginary parts of the Polyakov loop. The constants $`b_4`$ and $`𝒵_W`$ drop out, and one has a unique relation between this ratio of masses and the pressure. In particular, at the point of transition, using the previous results we find that

$$\frac{\stackrel{~}{m}_i}{\stackrel{~}{m}_r}=3,T=T_c^+.$$
(14)
This is our principal result. It is dependent upon the assumed form of the potential for $`𝒱(\mathrm{})`$, and would change if terms such as $`(|\mathrm{}|^2)^3`$ were included.

These two point functions in the Polyakov Loop Model are very different from those of ordinary perturbation theory. In perturbation theory, $`\mathrm{}_0`$ is near unity, and correlations are determined by multiple exchanges of $`A_0`$ fields. The mass of the $`A_0`$ field is the Debye mass, $`m_D^2g^2T^2`$. Expanding the exponentials, the real part of the Polyakov loop couples to $`\mathrm{tr}A_0^2`$, while that for the imaginary part couples to $`\mathrm{tr}A_0^3`$. Thus over large distances, $`x\mathrm{}`$,

$$\mathrm{}_r(x)\mathrm{}_r(0)\mathrm{}^2\frac{\mathrm{exp}(2m_Dx)}{x^2},$$
(15)
$$\mathrm{}_i(x)\mathrm{}_i(0)\frac{\mathrm{exp}(3m_Dx)}{x^3}.$$
(16)
Notice that the prefactors in front differ markedly from those of the Polyakov Loop Model; instead of $`1/x`$, they are $`1/x^2`$ and $`1/x^3`$, respectively, with the power of $`1/x`$ measuring the number of quanta exchanged.

If we ignore the difference in prefactors, even so the perturbative result for the mass ratio of (14) is not $`3`$, but $`3/2`$.

Measurements of the two point function of the real part of the Polyakov Loop have been carried out by Kaczmarek et al. . From the two point function of Polyakov loops, which is presumably dominated by that for the real part, the mass drops by about a factor of ten, from $`m/T2.5`$ at $`T=2T_c`$, to perhaps $`m/T.25`$ at $`T_c^+`$. We are not aware of any measurements of the imaginary part close to $`T_c`$.

There are also measurements by Bialas et al. for a $`SU(3)`$ gauge theory in $`2+1`$ dimensions . While the critical behavior in this model is that of a two dimensional system, and so can have characteristics special to a low dimension, for the Polyakov Loop Model in mean field theory, our predictions remain the same. These authors find that the ratio $`\stackrel{~}{m}_i/\stackrel{~}{m}_r`$ does increase from $`3/2`$ as the temperature approaches $`T_c`$.

In fact, the Polyakov Loop Model must be inapplicable at some temperature not too far above $`T_c`$. At high temperature, where $`\mathrm{}_01`$, the above formula give $`b_2=12b_3`$, and

$$\frac{\stackrel{~}{m}_i}{\stackrel{~}{m}_r}=\sqrt{\frac{3b_3}{1b_3}},T\mathrm{}.$$
(17)
The constant $`b_3`$ is not well determined, but for $`b_3<3/7`$, the above ratio is less than the perturbative value of $`3/2`$.

Thus we propose that the two point function of Polyakov loops can be used as a measure of the regime in which the Polyakov Loop Model applies, and the regime where perturbation theory applies.

What if the ratio of masses, (14), is wrong even at $`T_c`$? Besides including terms of higher order in the potential, it may also be necessary to include the charge two Polyakov loop, $`\mathrm{}_2`$. Since $`Z(3)`$ is a cyclic symmetry, a field with charge two is the same as one with charge minus one. The couplings of this loop with itself are identical to the couplings of the usual Polyakov loop, since the sign of the charge doesn’t matter. Unlike the charge one Polyakov loop, however, the charge two loop should always have a positive mass squared, in order to avoid condensation which breaks $`SU(3)SU(2)`$ . Thus one would assume that the charge two field, as a massive field, can be ignored. Nevertheless, the following coupling is $`Z(3)`$ symmetric:

$$\mathrm{}_1\mathrm{}_2+\mathrm{}_1^{}\mathrm{}_2^{}$$
(18)
This term mixes the charge one and charge two Polyakov loops, $`\mathrm{tr}𝐋\mathrm{tr}𝐋^2+\mathrm{}`$. Its coupling constant is directly measurable; if small, the charge two Polyakov loop can be ignored, and our prediction should hold.

Lastly, we note that the Polyakov loop may well couple weakly to other operators. Thus while in principle it should dominate all correlation functions at large distances (if it is the lightest state), this may be very difficult to see unless the operator couples strongly.


text:
# Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web

Beyond the information stored in pages of the World Wide Web, novel types of “meta-information” are created when they connect to each other. This information is a collective effect of independent users writing and linking pages, hidden from the casual user. Accessing it and understanding the inter-relation of connectivity and content in the WWW is a challenging problem . We demonstrate here how thematic relationships can be located precisely by looking only at the graph of hyperlinks, gleaning content and context from the Web without having to read what is in the pages. We begin by noting that reciprocal links (co-links) between pages signal a mutual recognition of authors, and then focus on triangles containing such links, since triangles indicate a transitive relation. The importance of triangles is quantified by the clustering coefficient  which we interpret as a curvature . This defines a Web-landscape whose connected regions of high curvature characterize a common topic. We show experimentally that reciprocity and curvature, when combined, accurately capture this meta-information for a wide variety of topics. As an example of future directions we analyze the neural network of C. elegans , using the same methods.

The Web is a graph  that is continuously being expanded by an enormous number of independent agents. Millions of users add pages in an uncoordinated way, but in doing so they must obey clear rules on how to address other pages . Beyond the information placed by the users directly in individual pages, their unified action creates a cooperative meta-information whose locus is in the connectivity of the network. By meta-information we mean here information that is based solely on the graph structure of the WWW, and which reveals strong contextual grouping. This type of information should be contrasted to that of a very informative but secluded page, that is an archive of information (a “wise hermit”). Further on, we will compare our new meta-information to earlier work.

The billions of pages and links of the WWW create a maze of confusing and almost unmanageable complexity. To navigate through it and to find pages of interest, users rely on the help of search engines . These send out small, automated programs (robots) that roam the Web, retrieve links and note keywords as they create a mirror image of the Web that can be stored within one room of storage data, ready for easy access. The Web remains intelligible to its human users precisely because it is constantly analyzed and monitored by these automatic agents. Robot activity dominates Web traffic and accounts for up to 70% of the total queries made at certain sites we studied. Because of the breadth of their search, robots obtain a clearer view of the Web than the common user.

It is therefore useful to adopt the perspective of robots, without having to define meaning or content, looking only at the identification tag of pages (URL addresses) and their links . To avoid the difficulty of having to know the complete Web graph we use robots which explore some locally visible pieces that can be found by starting from a given page and progressing along its links. An analogy may be drawn with classical neurobiology , where a neuron takes up dye which then traces out its connections.

Having defined our aim of revealing meta-information in the form of hidden thematic structures, we implement it by a novel combination of a number of key ideas: Clustering, co-links, triangles, and curvature. The clustering regroups a “home” page with the pages in its sub-directories. The co-links are then the result of independent agents linking their pages. Triangles capture transitivity, which we measure by the associated notion of curvature. Using it, we show that practically all the connective information depends on co-links. Thus, our method reveals a new geometric view of the locus of information in networks, which is not “put there” but “happens” as a collective effect.

In detail, we proceed as follows: The first step of our method is clustering . Once a certain number of pages have been found by our robot, we regroup them into a node by lumping together a “home” page with the pages in its sub-directories. This is useful because:

* Information within a given home site belongs to one contextual heading.
* The size of the graph is reduced by a factor of $`10^2`$$`10^3`$.
* Connective links that arise from physical proximity are eliminated, leaving the more relevant remote links.

Working henceforth exclusively with the clustered graph (like the one on the right of Fig. 1), we introduce the pivotal notion of co-link for a reciprocal connection between two nodes $`A`$ and $`B`$ ($`A`$ points to $`B`$ and $`B`$ points to $`A`$, the red link in Fig. 1). They are then deemed to be “congruent” (friends, or members in the same interest group).

Co-links are special because, while I can point to your page I cannot (in general) cause you to point to mine. Congruence therefore indicates an awareness by both nodes of the other’s existence and content, and a recognition of the other’s value to their own interests. Since congruence involves mutual recognition, we expect it to be a transitive property i.e., if sites $`A`$ and $`B`$ are congruent, and $`B`$ and $`C`$ are congruent, then $`A`$ and $`C`$ will be congruent with high probability, forming a triangle. Such triangles signal strong co-operative content, and would be extremely rare in any large random graph . To quantify the aggregation of triangles with congruent edges, we define the local curvature at a node $`n`$ by $`c_n=2t_n/((v_n1)v_n)`$. This quantity was termed the clustering coefficient in . Here, $`t_n`$ is the number of triangles containing $`n`$ as a corner, $`v_n`$ is the number of links leaving $`n`$ (the valence) and $`(v_n1)v_n/2`$ is the maximal number of possible triangles. We ignore in this the directionality of One-way links. If the graph is a tree, there are no triangles, and $`c_n=0`$ everywhere, while for any complete graph (where all nodes are mutually connected) $`c_n=1`$ everywhere.

To see that $`c_n`$ is indeed a quantity like curvature, we regard the simple geometric picture of Fig. 2: One way to detect that we are on a curved surface using local measurements is to walk a unit distance on a straight line in two different directions separated by a constant angle $`\alpha `$. Connecting the two endpoints completes a triangle, and the length of the third edge is determined by the curvature. On surfaces this relation of triangles to curvature is a natural generalization of the law of cosines, relating the angle at the apex and the three sides. For general metric spaces, such as infinite graphs, this relation is the basis of a mathematical definition of curvature  obtained by comparing triangles in a continuous metric to their counterparts embedded in standard manifolds.

The average number of triangles $`c_n`$ at a node $`n`$ is related to the average distance between any two of its nearest neighbors (say $`n^{}`$ and $`n^{\prime \prime }`$). This distance is measured by counting links in the shortest path from one node to another, namely $`n^{}`$ and $`n^{\prime \prime }`$. Because for co-links this is either $`1`$ ($`n^{}`$ and $`n^{\prime \prime }`$ directly connected, triangle exists) or $`2`$ (no triangle, need to go through node $`n`$), $`c_n=2r(n^{},n^{\prime \prime })`$, where $`r`$ is the distance. The average $``$ is taken over all pairs of nearest neighbors, so that the average triangle has sides 1, 1, $`r`$. In principle, for One-way links the distance $`r`$ may be a large number and can range all the way to infinity (no connection), but we shall still use $`c_n`$ as an upper bound on the connectivity.

We are not aware of a definition similar to the one of  for finite graphs with discrete metric, but it is still useful to view $`c_n`$ as the curvature of triangles with apex at $`n`$ (though $`c_n`$ is normalized to take values between $`0`$ and $`1`$), with $`c_n`$ being perhaps closer to a dimension measurement . Equipped with a metric (minimal number of hops between nodes) and a curvature, the graph of the WWW can be visualized geometrically. We shall say that it looks like a hyperboloid when it is tree-like, with exponential separation of branches that “fan out” . See Fig. 3. In contrast, a highly connected region looks more like a sphere that is “closed” on itself. Alternately, a random walk by the robot in the graph will tend to get trapped somewhat longer in highly curved regions.

Triangles tend to aggregate, creating interest groups of widely varying size (in terms of the number of members), but of small diameter. In general, the border of interest groups is expected to be a sharp interface, but sometimes different interest groups will connect one to another, typically via a single link (e.g., the member of the “butterfly collection” interest group who also belongs to the “origami” interest group). Our definition of curvature implies that such connecting nodes tend to be hubs, and are characterized by a low curvature.

While the meta-information of the graph has been noted before , and used for data mining in the influential works , we see now some differences with that work. That approach views a link as conferring “authority” and searches the WWW for “Authorities” and “Hubs” that point at them. Based on these ideas the successful search engine Google was designed; it also lead to the notion of “Community” . Similar investigations of the information content of linkages are common in other fields, such as studies of social  or paper citation  networks. However, in our case, “authorities” tend to have low curvature, while nodes recognized by peers get high curvature. (Belonging to two groups lowers the curvature by about a factor 2.)

We tested our general ideas in several Web crawls, encompassing over one million URL’s of which over three hundred thousand were actually accessed. The database is stored for offline analysis, while intermediate results are used to direct the further action of the robot. Large numbers of links in a page (indicating the page is a hub) tend to stall the crawl, and we followed at most 35 links per page, neither were .cgi, .jpg explored. As an aside, we note that .com sites seem to make little contribution to “cooperative content” and connect badly to others.

As the crawl proceeds, clustering according to Fig. 1 is implemented. To that end, links are determined to be local or remote. A local link is basically one inside a given site and any other link is remote. This decision is usually made by looking at the URL and using the known conventions for naming of pages inside a home directory (details can be obtained from the authors at http://mpej.unige.ch/~eckmann). The algorithm explores a page it encounters by following the local links down to depth $`d`$ (and perhaps $`u`$ upwards, links like “back to home page”).

Crawls are initialized by choosing a first site (the anchor) and fetching it. The links in a fetched page are identified and entered into the database. Our robot then fetches all the pages that these links point to. After exhausting the search down and up the database is clustered and the robot is sent out along the first remote link. It explores that node in a similar way, going down and up the newly found local links as before. Once that is done the robot returns to the first node and follows the next remote link, until all remote links at distance $`r=1`$ from the anchor have been followed. The robot can then be directed to explore $`r=2`$ or sequentially larger distances, if needed.

The breadth of crawls is shown in Table 1, while results from specific crawls are shown in Figure 3. The curvature was calculated for all nodes within a distance $`r=1`$ of the anchor, and for three types of graphs. The ‘Full’ graph includes all links that were found in the crawl, the ‘Congruence’ graph is composed solely of co-links (the red link of Fig. 1), and the ‘One-way’ subgraph is obtained from the full graph by removing all co-links (leaving only the black links).

Our main result, shown in Fig. 4, is that the average curvatures of the Congruence and Full graphs are very similar, while that of the One-way graph is lower by a factor ranging between $`2.5`$ and $`21`$. This means that removal of the co-links results in a dramatic decrease of the curvature. The curvature of the full graph is carried predominantly by triangles containing at least one reciprocal side. This curvature is not produced by triangles with three co-links alone, because of their small relative number, but rather from triangles that have a combination of co- and One-way links. To put the results of Fig. 3 in perspective, we note that the density of triangles (and average curvature as well) of a random graph tends to zero with the size of the graph .

For all experiments, the distribution of curvatures $`c`$ among the nodes of the Full graphs obeys a power law, $`c=(2.0\pm 0.2)v^1`$, where $`v`$ is the valence of the node. While the scaling is striking, we are not certain of its origin. It does cause highly connected nodes with high $`v`$ such as hubs and authorities to have, on average, a low curvature. This agrees with our intuition that such nodes contribute perhaps to global connectivity, but not to the local interest groups that curvature identifies.

While we consistently avoided any reference to content of sites in the crawl itself, to check our method a separate, objective criterion was needed. We therefore checked manually whether the co-links reveal contextual linkages, by reading in 784 nodes from our crawls (in most cases checking the name of the node sufficed). Indeed, we found that no less than $`75\%`$ to $`100\%`$ of nodes congruent to the anchor indeed relate to the same topic.

Going beyond the WWW, we examined the efficiency of curvature as a measure of thematic cohesion by studying three other networks. These are the neuronal network of the nematode C. elegans, the protein-protein interaction network of the yeast S. cerevisiae and the citation network of the mathematical-physics archive http://www.ma.utexas.edu/mp\_arc/. In each case we used an existing database to access and reconstruct the network, and as a control each had a separate, objective criterion by which related nodes were grouped into “themes”.

Our analysis of the neural network of the worm relies on classic work that used about 8,000 electron microscopy sections to trace directed neuronal connections. The control classification is the currently accepted association of neurons with organs found by both morphological and connective data , where the existence of triangles was indeed noted, though only incidentally.

In Fig. 5 we present the network of the brain of the nematode. We immediately note three connected components of high curvature, color coded to display the association with the major neural circuits, or organs. The elevated groups are the amphids, the motor neurons of the nerve ring and “other” sensory neurons of the head. The other circuits are either low-curvature (egg-laying and motor neurons of the ventral cord) or absent from the compilation  (tail ganglia). The amphids and nerve ring are particularly well separated into connected components of the congruence graph. Furthermore, we find that interneurons (CPU-like neurons) carry more curvature than sensory (input) or motor (output) neurons, which agrees with our intuition of how connections should distribute within the brain. Most co-links ($`61`$%) connect neurons that are within the same functional circuit ($`72`$% for co-links within triangles) while most of the One-way links ($`58`$%) connect between two different organs.

For the protein-protein interactions of the yeast we took the protein-protein interaction database http://dip.doe-mbi.ucla.edu/dip/Download.cgi, treating any interaction as a co-link (i.e., there are no One-way links). The control was taken from the functional classification given in the Yeast Protein Databank (YPD) at http://www.proteome.com/databases/YPD/YPDcategories/Functional\_Categories.html. We found that proteins within the same connected groups of high curvature almost always ($`77`$% of the cases) belonged to the same functional grouping of the YPD. At $`c_n0.15`$ there are $`34`$ such groups, that include between $`3`$ to $`18`$ members, with an average of 5 proteins per group, (data not shown).

In the case of the Mathematical Physics archive, we used the archive http://www.ma.utexas.edu/mp\_arc to define a network of citations between authors in the same field. A co-link exists if author A cites author B (in any paper within the archive) and author B cites A in any paper of his, while co-authors are automatically co-linked. Note that our definition of co-links is fundamentally different from the co-citations defined in , since there no reciprocal recognition exists. The control we used here was more problematic, relying on scanning manually all conference pages listed at the International Mathematical Physics Association homepage, and including an author in a group (e.g., “Quantum mechanics”, “Field theory” or “Statistical mechanics”) if she spoke under that topic in any of the conferences. However, we were able to classify only about $`400`$ of the $`1700`$ authors (since not every author is talking at these conferences). As before, high curvature selected out the groups we found manually, with $`5`$ of the $`20`$ or so topic groups we defined very strongly represented and clearly identified (data not shown). Again, “authorities”, which in this case are very polyvalent scientists, have lower curvature than specialists in a small field, and serve rather as hubs.

Our discovery opens a number of new possibilities for studying highly assembled complex structures in general, perhaps even the brain. First, the introduction of geometry frees us from the subjectivity of contextual concepts, such as meaning, content, and the like. The locality develops a different direction than global notions like scaling in the WWW and the “small-world” effect. Second, the concept of congruence shows the usefulness of combining geometry with selective action in probing sophisticated structures, including C. elegans. In particular, we have seen how a very simple dynamical rule – the search for congruence – radically changes our global view of the Web, replacing statistical aspects with unsuspected relations which can be found only by looking at combined, independently built, pathways in the Web. Our approach can certainly be refined and extended in the Web, but should prove useful in many other contexts.

Our study further shows that robots perceive the Web differently than the people who actually write and use the pages. Our robots go back and forth between various sites, gaining a more coherent view of their relations. We have shown that the geometric properties of the space in which they roam and the landscape that they reconstruct reveal new connective meta-information, hidden from the common user.

What can one expect in the future? Other forms of meta-information, not necessarily arising from connectivity, will certainly be found in the WWW and other complex networks. The dynamics of developing interest groups is also an important issue  that may involve rapid fusion processes . From a mathematical perspective, we have demonstrated the need for concepts of local curvature in graphs. Our definition of curvature seems a useful beginning to elicit Web properties, and is easily generalized to balls of radius $`r=2`$ (next-nearest neighbors) or more, as well as to simplices like tetrahedra. But more advanced geometric concepts, measuring non-commutativity in the order of visiting sites, might be needed in the future.

We are grateful for numerous discussions with our colleagues in Geneva and Rehovot, and for special help by A. Haefliger and D. Ruelle. We also thank P. Blekken for help with Coin. This work was partially supported by the Fonds National Suisse and the Minerva Foundation, Munich.