The Lower, The Better

2002 Skadron Prize In Computational Physics

A model for a network of neurons (i.e., nerve cells) inside a brain can mimic a process of associative memory (i.e., associating or matching a given input pattern with a memorized pattern, for example, a photographic image of your parents with their image memorized in your brain.) In this model, this memory process is represented by a process of minimizing the following function:

H = - 1/2 Sumi=1,N Sumj=1,N Jij Si Sj

by varying N variables, S1, S2, S3, ..., and SN.

Each variable Si represents the state of the i-th neuron:

Si = +1, if the neuron is excited and firing electrical signals to other neurons,

Si = -1, if the neuron is not excited.

Jij prescribes how the j-th neuron affects the i-th neuron: Jij is roughly proportional to an electrical potential change in the i-th neuron when the j-th neuron is firing electrical signals to the i-th neuron. Jij also satisfies

Jii = 0 and Jij = Jij.

We will assign each Jij one of the following two values:

Jij = +1 or -1.

If the value for each Jij is chosen randomly between these two values, then there may be many ways of assigning values, either +1 or -1, to Si that minimize the above function H.

For this year's Skadron prize, we ask you to come up with a subroutine that finds one of these minimum values. The goal is therefore to find the values of Si that minimize H for values of Jij randomly selected by the main program, which will be provided by the department.

More Specifically

Write a FORTRAN subroutine "minimize.f" (if you prefer to program in C, submit a C function "minimize.c") that must start with the following 2 lines:

subroutine minimize (IS, Jij, N) dimension IS(N), Jij(N,N)

where

IS is an integer array variable whose size is N, the total number of the neurons. IS(i) represents Si and takes a value of either +1 or -1;

Jij is a two-dimensional integer array variable whose size is N by N. Jij(i,j) represents Jij and takes a value of either +1 or -1 (or 0). The values for Jij are randomly assigned by the main program.

For the contest, we will use the following value for N:

N = 200

However, your subroutine should be able to run for any arbitrary value of N.

The prize committee will run your subroutine "minimize" with the main program, which checks if the value for each Si selected by your subroutine is either +1 or -1. Your subroutine will be given three sets of Jij and the main program calculates the function H for these three sets. The first prize goes to the contestant whose subroutine gives the lowest "average" value for H. Your subroutine must also complete its computation for three sets of Jij within 5 minutes on Entropy.

CAUTION: Do not attempt to examine every possible way of assigning values to Si to find the one with the lowest value for H, simply because it will certainly take more than 5 minutes.

To test your subroutine "minimize.f":

1. Copy the main program "skmain02.f" available on "Entropy" to your account:

   cp /home/hmb/skmain02.f skmain02.f

2. Compile and run your subroutine with the main program:

   xlf90 -O skmain02.f minimize.f
   a.out

To test your C function "minimize.c":

1. Copy the main program "skmain02.c" available on "Entropy" to your account: cp /home/goderya/skmain02.c skmain02.c

2. Compile and run your subroutine with the main program:

   xlc -O skmain02.c minimize.c
   a.out

Prizes

$200 for the first place, $100 for the second place.

Who can participate

Physics majors at ISU.

Deadline

4:00pm on Tuesday, April 30, 2002.