Документ взят из кэша поисковой машины. Адрес оригинального документа : http://acat02.sinp.msu.ru/presentations/jadach/Foam-ACAT02.ps Дата изменения: Sat Jul 6 17:26:39 2002 Дата индексирования: Mon Oct 1 20:20:43 2012 Кодировка: Windows-1251

ACAT2002,
Moscow
1
FOAM:
general
purpose
Monte
Carlo
Cellular
Algorithm
S.
Jadach
Institute
of
Nuclear
Physics,
Krak'
ow
(Cracow),
Poland
Outline: .
Introduction
and
motivation
.
Cellular
algorithm
of
FOAM
.
Examples
of
numerical
results
.
Conclusions
Work
supported
in
part
by
the
European
Community's
Human
Potential
Programme
under
contract
HPRN-CT-2000-00149
``Physics
at
Colliders'',
and
NATO
grant
PST.CLG.977751.
These
and
related
slides
on
http://home.cern.ch/jadach
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
2
MC
integration
#=
MC
generation
#=
MC
simulation
MY
AIM#
Monte
Carlo
Simulation
(w=1
events);
MC
integral
is
a
byproduct
General
purpose
means:
.
applies
to
arbitrary
(wide
range)
user-distributions
.
works
as
a
BLACK
BOX
,
as
a
component
or
stand-alone
(MINUIT
minimization
program
of
F.
James
is
a
model
to
follow
for
me.)
``Adaptive''
is
almost
a
synonym
of
``general
purpose''.
e-Print:
physics/0203033
describes
on
60
pages:
.
the
entire
algorithm,
all
variants/options
.
program
architecture,
.
how
to
use
the
program
.
and
results
of
the
numerical
tests.
Here
I
shall
cover
mainly
the
algorithm.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
3
Programs,
available
from
the
author,
to
appear
in
Comp.
Phys.
Commun.
Foam
v2.02,
c++
:
fully
object
oriented,
dynamic
memory
allocation,
unlimited
number
of
cellsN
c
and
dimension
nDim+kDim,
Simplices,
hyperrectangles
and
Cartesian
products
of
them
available.
For
hyperrectangles
low
memory
consumption
is
the
default
option.
No
persistency.
Foam
v2.02,
c++:
variant
using
ROOT
package
(R.
Brun
et.el.)
Implements
persistency
of
the
class
TFOAM
using
automatic
streamers
of
ROOT!
MCell
v2.02,
f77:
with
up
to
1Mega
cells
is
specialized
for
higher
dimensions,
n
#
20,
hyperrectangular
cells
only.
(Both
f77
versions
are
frozen!)
Foam
v2.02,
f77
:
withN
c
#
10000
cells,
is
aimed
for
up
to
six-dimensions.
Upgraded
and
improved
with
respect
to
1.x:
both
simplices
(n
#
5)
and
hyperrectangles
(n
#
10)
available.
Low
memory
consumption
optionally.
Other
recent
improvements:
.
Provisions
for
``multibranching''
(multichannel)
algorithm,
with
automatic
adjustment
of
branches
(similar
to
Kleiss&Pittau).
.
Possibility
to
start
FOAM
from
SINGLE
simplex
instead
of
unit
hyper-cube.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
4
Works
related
to
General
Purpose
MC
simulation
(integration)
problem
VEGAS
and
the
like
.
G.P .
Lepage,
J.
Comput.
Phys.
27,
195
(1978).
.
T.
Ohl,
Vegas
revisited:
Adaptive
Monte
Carlo
integration
beyond
factorization,
Comput.Phys.Commun.
120
(1999)13,
eprint:
hep-ph/9806432.
.
S.
Kawabata,
Comp.
Phys.
Commun.
88,
309
(1995). Cellular:
.
Earlier
unpublished
trials
in
80's
by
S.
Kawabata,
R.
Kleiss
and
S.
Jadach.
.
G.
I.
Manankova,
A.
F.
Tatarchenko,
and
F.
V.
Tkachev,
MILXy
way:
How
much
better
than
VEGAS
can
one
integrate
in
many
dimensions?,
1995,
a
Contribution
to
AINHEP-95,
Pisa,
Italy,
Apr
3-8,
1995
(extended
version).
.
Keijiro
Tobimatsu
and
Setsuya
Kawabata,
``Multi-dimensional
Integration
Routine
DICE
for
Vector
Processor''
Research
report
of
Kogakuin
University,
1996,
No.
85.
.
E.
de
Doncker
and
A.
Gupta,
``Multivariate
Integration
on
Hypercubic
and
Mesh
Networks'',
Parallel
Computing
24
(1998)
1223.
.
S.
Jadach,
Comput.Phys.Commun.
130,
244
(2000);
and
``Foam:
A
general
purpose
cellular
Monte
Carlo
event
generator''
e-Print:
physics/0203033.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
5
General
features
of
General
Purpose
Monte
Carlo
Simulators
(GPMCS)
Inevitably
the
GPMCS
has
to
work
in
2
stages:
exploration
and
generation.
During
exploration
GPMCS
is
``digesting''
the
entire
shape
of
the
n-dimensional
distribution
#(x1
,x2
,
...xn
)
to
be
generated
and
memorize
it
as
efficiently
as
possible
using
all
CPU
power
and
memory
available.
Obviously,
for
the
memorized
#
#
(x
1
,x2
,
...x
n
)
a
method
of
the
MC
generation
of
the
points
# x
exactly
according
to
#
#
(#
x),
has
to
be
available.
The
quality
of
the
distribution
of
the
weight
w
=
#/#
#
for
events
in
the
generation
(small
variance,
good
ration
of
maximum
to
average,
etc.)
is
determined
by
the
algorithm
of
the
exploration.
In
other
words,
the
``target
weight
distribution''
in
the
generation
is
determining
the
algorithm
of
exploration.
The
GPMCS
programs
will
be
always
limited
to
``small
dimensions''.
With
presently
available
computers
``small''
means
in
practice
n
<
10
(up
to
n
<
15
for
certain
function).
This
is
already
not
so
bad!!!
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
6
Cellular
exploration
of
the
distribution
The
most
obvious
method
to
minimize
the
variance
(or
maximum
weight)
of
the
target
weight
distribution
in
generation
(proposed
already
some
40
years
ago)
is
to
split
integration
domain
into
many
cells,
such
that
#(# x)
is
approximated
by
constant
#
#
(#
x)
within
each
cell.
This
is
a
cellular
class
of
general
purpose
MC
algorithms.
(I
think
that
``stratified
sampling'',
used
in
the
literature,
has
a
narrower
meaning.)
FOAM:
shape
of
cells,
how
to
cover
space
with
cells?
Three
shapes
of
cells
are
used
pure
simplices,
pure
hyperrectangles
and
Cartesian
products
of
them.
They
can
be
rather
easily
and
efficiently
parametrized.
The
system
of
cells
can
be
created
all
at
once
(like
in
Vegas)
or
in
a
more
evolutionary
way,
by
the
``split
process''.
In
the
Foam
algorithm
we
rely
on
the
binary
split
of
cells.
(Choice
of
a
cell
to
be
split
driven
by
target
weight
distribution.)
The
binary
split
assures
automatically
full
coverage
of
the
space,
simply
because
the
primary
``root
cell''
coincides
with
the
entire
integration
domain.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
7
Variance
reduction
versus
maximum
weight
reduction
In
construction
of
the
FOAM
algorithm
I
have
put
most
effort
on
the
minimization
of
the
ratio
of
the
maximum
weight
to
the
average
weight
wmax/#w#.
This
parameter
is
essential,
if
we
want
to
transform
w-ted
events
into
w
=
1
events,
at
the
latter
stage
of
the
MC
generation.
Minimizing
maximum
weight
is
not
the
same
as
minimizing
variance
#
=
#
#w
2
#-
#w#
2
.
Minimizing
wmax
more
difficult?
In
FOAM
minimizing
variance
is
also
implemented
and
optionally
available.
It
can
be
useful
if
case
them
w-ted
events
are
acceptable.
Next
slide
shows
two
examples
of
the
weight
distribution
evolution
in
the
Foam,
when
adding
more
and
more
cells.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
8
Generation
weight
distribution:
minimization
of
variance
0:50
1:00
1:50
2:00
0:00
\Delta
10
4
1:00
\Delta
10
4
2:00
\Delta
10
4
3:00
\Delta
10
4
4:00
\Delta
10
4
0:50
1:00
1:50
2:00
0:00
\Delta
10
5
0:50
\Delta
10
5
1:00
\Delta
10
5
1:50
\Delta
10
5
0:50
1:00
1:50
2:00
0:00
\Delta
10
5
1:00
\Delta
10
5
2:00
\Delta
10
5
3:00
\Delta
10
5
Number
of
cells:
200,
2k,
20k
Generation
weight
distribution:
minimization
of
maximum
weight
0:50
1:00
1:50
2:00
0:00
\Delta
10
4
2:00
\Delta
10
4
4:00
\Delta
10
4
6:00
\Delta
10
4
8:00
\Delta
10
4
0:50
1:00
1:50
2:00
0:00
\Delta
10
5
0:50
\Delta
10
5
1:00
\Delta
10
5
1:50
\Delta
10
5
0:50
1:00
1:50
2:00
0:00
\Delta
10
5
0:50
\Delta
10
5
1:00
\Delta
10
5
1:50
\Delta
10
5
2:00
\Delta
10
5
2:50
\Delta
10
5
Number
of
cells:
200,
2k,
20k
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
9
Cell
split
algorithm:
covers
both
(a)
wmax
and
(b)
variance
minimization
We
define
two
auxiliary
distributions
#
#
(x)
and
#loss
(x)
related
to
integrand
#(x).
Both
are
constructed
together
with
the
foam
of
cells,
in
the
exploration
process.
(1)
EXPLORATION
of
#(x)
and
BUILD-UP
of
Foam
of
cells
:
#loss
(x)
and
#
#
(x)
are
evolving
in
the
process
of
the
division
of
cells.
Rloss
=
#
#loss
d
n
x
is
minimized
in
the
same
process.
(2)
MC
event
generation:
Events
are
generated
according
to
#
#
(x).
R
#
=
#
#
#
d
n
x
is
known
exactly.
R
=
R
#
#w#
#
where
w
=
#/#
#
.
The
average
#...#
#
is
over
events
generated
according
to
#
#
.
(a)
Minimization
of
wmax
#
#
(x)
#
maxy#Celli
#(y),
for
x
#
Cell
i
,
the
``ceiling
function''.
Rloss
=
#
d
n
x
[#
#
(x)-
#(x)]
=
#
d
n
x
#loss
(x),
Note
that
rejection
rate
in
final
MC
run
=Rloss/R.
(b)
Minimization
of
of
variance
#
#
(x)
#
#
##
2
#
i
,
for
x
#
Cell
i
.
The
average#...#
i
is
over
i-thCell
assuming
flat
distribution.
#loss
(x)
#
#
##
2
#
i
-###i
,
for
x
#
Cell
i
.
Final
MC
variance
is
just#
Rloss
.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
10
Two
Rules
governing
binary
split
of
a
cell
Each
split
of
a
Cell:
#
##
#
+#
##
should
decrease
totalR
loss
.
R
#
# loss
+R
#
## loss
<<
R
#
loss
How
to
get
the
best
total
decrease#Rloss
?
[1]
We
always
split
``the
worst''
cell
with
the
biggestR
loss
(or
with
prob.
#
Rloss
)
[2]
Position/direction
of
a
plane
dividing
a
parent
cell
into
two
daughter
cells
is
chosen
to
get
the
smallest
totalR
loss
.
How
do
we
split
a
cell
into
two
daughter
cells?
General
method
relies
on
the
small
MC
exercise
on
which
events
are
generated
with
flat
distribution,
weighted
with
#
and
projected
onto
n
(simplical
case)
or
n(n+
1)/2
(h-rect.
case)
of
the
cells.
Resulting
histograms
are
analysed
and
the
best
``division
geometry''
found,
for
which
the
estimate
of#Rloss
is
calculated.
See
next
slides...
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
11
Geometry
of
n-dim.
Simplical
Cell
division,
3-Dim.
case
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000 1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
i j
new
vertex
daughter
2
daughter
1
Parent
simplex
Pair
of
vertices
xi
and
xj
is
chosen
and
a
new
vertex
Y
is
put
somewhere
on
the
line
in
between:
Y
=
#xi
+(1-
#)xj
,
0
<
#
<
1
Two
daughter
simplices
are
defined
with
the
list
of
vertices:
(x1,
x2,
...,
xi-1,Y,
xi+1,
...,
xj-1,xj
,xj+1,
...,
xn,
xn+1),
(x1,
x2,
...,
xi-1,
xi,
xi+1,
...,
xj-1,Y,xj+1,
...,
xn,
xn+1).
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
12
Geometry
of
n-dim.
Simplical
Cell
division,
3-Dim.
case
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000
0000000000000000000000000000000 1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111
1111111111111111111111111111111 00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000 11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
i j
Y
X
How
do
we
choose
(i,
j)
pair
and
the
value
of
#?
Short
sample
of
the
MC
events
(100-1000)
is
generated
#
cell.
Each
MC
point
projectedX
#Y
onto
a
given
edge
(i,
j),
i
#=
j:
Y
=
#ijxi
+(1-
#ij
)xj
,
#ij
(X)
=
|Det
i
|
|Det
i
|+|Det
j
|
,
Deti
=
Det(r1,
...,
ri-1,
ri+1,
...rn
,
rn+1),
Detj
=
Det(r1,
...,
rj-1,
rj+1,
...rn
,
rn+1),
rk
=
xk
-X,
where
Det(x1,x2,
...,
xn)
determinant.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
13
Choice
of
the
best
division
edge,
Simplical
3-Dim.
case
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000 11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111 0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000
0000000000000000000000000000 1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111
1111111111111111111111111111 00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000 11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
11111111111111111111111111111111
1
2
3
4
(3,4)
(1,4)
(1,2)
(2,3)
(2,4)
How
do
we
select
(i,
j)?
out
of
n(n-1) 2
possibilities.
For
each
(i,
j)
the
dN/d#
is
histogrammed,
and
its
LOSS
functionalR
loss
is
estimated.
The
edge
(i,
j)
with
the
biggest
LOSS
is
selected!
For
the
cell
division
#
is
read
from
the
histogram.
#
is
always
a
rational
number,
n/Nbin
.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
14
Binary
split
2-dim.
example
u
1
u
2
u 3
u 4
u
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
4
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
5
0:250
0:500
0:750
1:000
0:000
0:250
0:500
0:750
1:000 dN -
-
0:250
0:500
0:750
1:000
0:000
0:250
0:500
0:750
1:000 dN -
-
0:250
0:500
0:750
1:000
0:000
0:250
0:500
0:750
1:000 dN -
-
.
Integrand
covers
narrow
strip
along
edges.
.
We
intend
to
split
upper
triangle.
.
1000
w-ted
events
are
generated
and
projected
onto
3
sides
of
the
parent
triangle.
.
3
Projections
are
analyzed.
.
Chosen
is
the
cell
with
the
smallestRloss
(middle
plot).
.
Two
resulting
daughter
triangles
are
shown
at
leftmost
plot.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
15
2-dimensional
example
of
binary
split:
projection
on
one
of
edges
0:25
0:50
0:75
1:00
0:00
0:25
0:50
0:75
1:00 ae(x)
x
Old
ae
0
New
ae
0
OLD
I
loss
New
I
loss
New ?
.
Projected
integrand
#(x).
.
Old
#
#
for
parent
cell
(majorizing
#(x)).
.
New
#
#
for
two
daughter
cells.
.
OLDRloss
all
area
above
red
line,
for
the
parent
cell.
.
NewRloss
between
red
line
and
New
#
#
,
for
2
daughters.
.
Obviously
I
#
New
<
I
#
Old
,
the
division
point
#
is
chosen
to
MINIMIZE
THE
LOSS
functional/integralR
loss
!
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
16
Evolution
of
simplical
foam
at
2-dim.
u
1
?
2
u
3
?
4
u
5
?
6
u
7
u
8
e
e
e
e
e
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e e
e
e
e
e
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
4
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
6
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
8
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
9
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
10
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
11
?
1
?
2
u
3
?
4
?
5
?
6
?
7
?
8
?
9
?
10
?
11
?
12
?
13
?
14
?
15
u
16
?
17
?
18
?
19
?
20
u 21
?
22 ?
23
u
24
u
25
u 26
u
27
u
28
u
29
u
30
u
31
u
32
u
33
u
34
u
35
u
36
u
37
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
14
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
22
hhhhhhhhhhhhhhhhh e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
27
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\PhiQ
Q
Q
Q
Q
Q
Q
Q Q
Q
Q
29
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
31
T T
T
T T
T T
T T
T T
T
T T
T T
T T
T T
T
T T
T T
T T
T T
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
32
hhhhhhhD
D
D
D
D
D
D
D
D
D
D
\Delta
\Delta \Delta \Delta
\Delta
\Delta
\Delta
\Delta \Delta \Delta
\Delta
36
((((((((((((((( !
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
39
C C C C C C C C C C C C C C C C C C C C C C C
l
l
l
l
l
l
l
40
(((((((((((((((((((((((((( \Gamma
\Gamma
\Gamma
43
B
B
B
B
B
B
B
B
B
B
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
44
E
E
E
E
E
E
E
E
E
E
E B B B B B B B B B B \Gamma \Gamma \Gamma
45
,
,
,
,
D
D
D
D
D
D
D
D
D
D
D
D
D 46
,
,
,
,
,
,
,
,
fi
fi
fi fi
fi
fi fi
fi
fi fi
fi
fi
fi fi
fi
fi fi
fi
fi fi
fi
fi
47
e
e
e
e
e
e
e
e e
e e
e e
e e
e e
e
e
e T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T E E E E E E E E E E
48
e
e
e e
e
eE
E
E
E
E
E
E
E
E
E
\Gamma
\Gamma
\Gamma
\Gamma
49
A
A
A
A
A
A
A
A
A
A
\Phi
\Phi
\Phi
\Phi E E E E E E E E E E E
50
((((((((((((((((
b
b
b b
b b
52
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b (
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
53
e
e
e
e D D D D D D D D D D D D D D D D D D D D D D D D
54
e
e
e 55
!
!
!
!
!
!
!
!
!``````` (
(
(
(
(
(
(
(
(
(
(
(
(
(
(
56
`````````` !
!
!
!
!
!
!
!
!
57
a
a
a
a
a
a
a
a
a
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi A A A A A A A
58
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
a
a
a
a
a
a
a
a
a A A A A
59
C
C
C
C
C
C
C
C
Cl l
l l l
l l \Gamma
\Gamma
\Gamma
\Gamma
60
C C C C C C C C C
\Gamma \Gamma \Gamma
61
hhh\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta '
'
'
'
'
'
'
'
'
'
62
hhhh'
'
'
'
'
'
'
'
'
'
,
,
,
,
,
,
,
,
,
,
,
,
63
///////////////fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
64
hhhhhhhhhhhhfi fi
fi
fi
fi
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
65
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Gamma \Gamma
66
\Gamma \Gamma
67
P
P
P
P
P
P
P
P
P
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
68
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
P
P
P
P
P
P
P
P
P
69
?
1
?
2
?
3
?
4
?
5
?
6
?
7
?
8
?
9
?
10
?
11
?
12
?
13
?
14
?
15
?
16
?
17
?
18
?
19
?
20
?
21
?
22 ?
23
?
24
?
25
?
26
?
27
?
28
u
29
u
30
?
31
?
32
?
33
?
34
?
35
u
36
?
37
?
38
?
39
?
40
u
41
?
42
?
43
?
44
?
45
?
46
?
47
?
48
?
49
?
50
?
51
?
52
?
53
u
54
?
55
u
56
?
57
?
58
?
59
u
60
?
61
u
62
?
63
?
64 ?
65
?
66
u
67
?
68
?
69
u
70
u 71
?
72
?
73
u
74
?
75
u
76
?
77
u
78
?
79
u
80
u
81
u
82
u
83
u
84
u
85
?
86
u
87
u
88
u
89
?
90
u
91
u
92
u
93
u
94
u
95
u
96
u
97
u 98
u
99
u
100
u
101
u 102
u
103
u
104
u 105
u
106
u 107
u
108
u
109
u
110
u
111
u
112
u
113
u
114
u
115
u
116
u
117
u
118
u
119
u 120
u
121
u
122
u
123
u
124
u
125
u
126
u
127
C C C C C C C C C C C C C C C C C C C C C C C
l
l
l
l
l
l
l
40
(((((((((
X
X
X
X
X
X
X
\Gamma
\Gamma
\Gamma
71
e
e
e
e
e
\Phi
\Phi
\Phi
\Phi E E E E E E
82
A A A A A A A E
E
E
E
E
E
E
E
E
E
\Gamma
\Gamma \Gamma
84
C
C
C
Cl l
l l l
l l X
X
X
X
X
X
86
е
е
е
е
е
е
\Gamma \Gamma
96
ш
ш
ш
ш
ш
ш
((((((((((( !
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
98
\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega
D
D
D
\Delta
\Delta \Delta \Delta
\Delta
\Delta
\Delta
\Delta \Delta \Delta
\Delta
100
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Delta
\Delta
\Delta
\Delta
\Delta '
'
'
'
'
'
'
'
'
'
102
hhh\Delta
\Delta
\Delta
\Delta
\Delta
\Delta \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
103
,
,
,
,
,
,
,
,
\Pi
\Pi
\Pi
\Pi
'
'
'
'
'
'
'
'
'
'
'
105
Z
Z
Z
Z
Z
Z
Z
!
!
@ @
@ @ @
@
111
J J J J \Gamma \Gamma \Gamma
113
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a \Phi
\Phi
\Phi
\Phi
115
e
e
e
e
e
e
e
Q
Q
Q
Q
Q
Q
Q
Q Q
Q
Q
117
\Theta \Theta \Theta
\Theta \Theta \Theta \Theta
\Theta \Theta \Theta \Theta
\Theta \Theta \Theta \Theta fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi
fi \Gamma
\Gamma
\Gamma
118
E
E
E
E
E
E
E B B B B B B B B B B l
l
l
120
P
P
P
P
P
P
hhhhhhhh \Phi
\Phi
123
c c D D D D D D D D D D
127
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
e
e
e
e
e 128
hhhhhhhhhhhhhhhhh e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e \Theta \Theta
\Theta \Theta \Theta \Theta \Theta
\Theta \Theta \Theta \Theta \Theta
\Theta \Theta
129
e
e
e
e B B B B B B B B B B
130
%
%
%
%
% fi fi fi
fi
!
!
!
133
\Lambda
\Lambda
\Lambda
\Lambda
\Lambda
\Lambda
e
e
e 134
\Lambda \Lambda \Lambda \Lambda \Lambda \Lambda
135
H
H
H
H
X
X X X X X
136
b
b
b
XXXXXXX 138
`
`
`
`
`
`
140
143
hhhhhhhhhhhhhhhhhhhhhhhh 144
A
A
A
A
A
A e
e e e
e j j
146
A
A
A
A
j
j E E E E E
147
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
149
!
!
!
!
!
!
!
!
!
!
!
!H H
H H
H (
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
150
b
b
b
b
b
b
b
b
b
b
b
b !
!
!
!
!
!
!
!
!
!
!
!
151
Q Q
D
D
D A A A A
153
```` j
j
j
j
154 j
j
j
j %
%
%
%
%
155
fi
fi
fi
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
156
hhhhhhhhhhhhfi fi
157
?
?
?
?
?
?
D
D
D \Theta \Theta
\Theta \Theta
\Theta \Theta
\Theta \Theta
158
,
,
,
,
D
D
D
?
?
?
? ? ?
159
Z
Z
Z
Z
\Phi
\Phi
\Phi A A A A
160
@
@
@
@
@
@
Z
Z
Z
Z A A A
161
/////
b
b
162
L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L L
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
164
T T
T
T T
T T
T T
T T
T
T T
T T
T T
T T
T
T T
T T
T T
T T L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
\Gamma
\Gamma
\Gamma
\Gamma
165
j
j
j
j
j
`` !
!
!
!
!
!
!
166
e
e
e
e
e
e
e
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
168
B
B
B
B
B
B
B
B
B
B e
e e
e
e
e
e \Gamma \Gamma \Gamma
169
fi
fi fi 170
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
``````` (
(
(
(
(
(
(
(
(
(
(
(
172
!
!
!
!
!
!
!
!
! \Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
(
(
(
173 e
e
e
e
H
H
H
H \Gamma \Gamma
174
e
e
e
e
a
a
a D D D
176 Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
a
a
a
a
a
a
e
e
e
e
177
fi
fi
B
B
B
B
B
B
B
B
B
B C C C C C C C C C C C
178
E
E
E
E
E
E
fi fi C C C C C
179
e
e
\Phi
\Phi
\Phi
\Phi
180
h
h
h
h
h
h
h
h
e e
181
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
182
j
j
j
j
j
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
,
,
,
,
,
,
,
,
,
,
,
,
184
h
h\Gamma
\Gamma
\Gamma
j
j
j
j
j
185
((((( \Phi
\Phi
\Phi
\Phi
\Phi
186 \Phi
\Phi
\Phi
\Phi
\Phi ш
ш
ш
ш
ш ш
187
e e
e A
A
A
A
A
A
A D D D D D
188
``
``
`` D
D
D
D
D
\Gamma \Gamma 189
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
190
/////////////// \Gamma
\Gamma
\Gamma
\Gamma
191
e
e
e e
e
e e
e
e e
e
e e
e T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T L L L L L L L L L L L L L L L L
192
e
e
e e e e
e L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L E E E E E E E E E E
193
C
C
C
C
C
C
C
C
C
C
C D D D D D D D D D D D D D D
194
c cC
C
C
C 195
(((((((((( 196
(((((((
е
е
е
е
е
е
е
197
h
h
h
h
h
h
h
h
h
h
h
h
h
hhhhhhhhhhhh 198
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
fi
fi fi
fi fi
fi
fi fi
fi fi
fi
fi fi
fi
fi fi
200
'
'
'
'
'
'
'
'
'
'
' \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
fi
fi fi
fi
201
b b
C C C J
J
J
J
202
C C C C C C C
b
b
203
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
hhhhhhhhhhhhhhhhhhh \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
204
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
hhhh E E E E E E E E E E E E E E E E E E
205
е
е
е
ее
hhhhhh 206
еее
h
h
h
h
h
h b b b
207
a
a
l
l
l
l
l
Z
Z Z
Z
Z
Z
Z
209
h
h
h
h
h
h
h
h
h
h
h
h A A
210
A A
\Gamma \Gamma 211
h h'
'
'
'
'
'
'
'
'
' %
%
%
%
%
%
%
%
%
%
%
212
%
%
%
%
%
%
%
%
%
%
% \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
213
214
/
/
/
/
215
b b
216
((((((((((((((((
b b b
217
P
P
P
h
h
h
h
h
h
h
h
h
h
hhhhhhhhhhhhh 218
h
h
h
h
h
h
h
h
h
h
h P
PP
219
P
P
P
P
220
`
`
`
`
`
`
`
`
`
`
P
P P
P P
P
221
(((((((( 222
P
P
P
P
(
(
(
(
(
(
(
(
223 224
е
е
е
е е
е
225
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
%
% %
226
%
%
%
/
/
/
/
/
/
/
/
/
/
/
/
/
227
i
i
i
i
i
i
///////////// (
(
(
(
(
(
(
( 228
i
i
i
i
i
i
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
229
a
a
a
a
a
a
a
a
a
a
a
a
\Phi
\Phi
\Phi
\Phi
\Phi
e
e
e
e e
e e
230
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phia
a
a
a a
a
a
a
a
a a
a
231
l
l
l
\Gamma
\Gamma
232 h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
l l l
233
h h h h
234
h
h
h
h
235
\Theta
\Theta
D
D
D
D
D
D
D
D
236
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
237
L
L
L
L
l l
l \Gamma \Gamma
238 E
E
E
E
E L L L L
239
hhhhhhD
D
D
D
D
D
D
D
D
\Delta
\Delta
\Delta \Delta \Delta
\Delta
\Delta
\Delta
\Delta
240
h h\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta
\Delta\Omega \Omega \Omega \Omega \Omega \Omega \Omega \Omega
241
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
242
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh \Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
\Phi
243
fi
fi
```` i
i
i
i
i
244
fi
fi
i
i
i
i
i j
j
j
j
j
245
\Phi
\Phi
\Phi
l l
246
a
a
a
a
a
a
a
l l l l
247
C
C
C e e e e P
P
248 C
C
C
PP \Gamma \Gamma
249
r
r
r
r
r
r
r r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
r
Number
of
cells=
10,
70,
250,
2500.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
17
Evolution
of
hyper-rect.
foam
at
2-dim.
2
4
7
9
10
11
10
15
17
19
20
29
30
32
34
35
36
38
40
43
44
46
48
49
50
51
52
54
55
56
57
58
59
61
62
63
64
66
67
68
69
40
43
46
64
77
86
89
91
92
94
97
98
100
105
108
110
115
117
119
121
122
124
126
129
130
133
134
137
138
139
140
141
142
143
146
148
149
151
152
153
154
155
156
157
158
159
161
162
163
164
165 167
168
169
170
171
173
174
175
177
178
179
181
182
183 185
186
187
188
189
190
192193
194
195
196
198
199
200
201
202
204
205
206
207
208
209
210
211
212
214
215
216
217
218
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
Number
of
cells=
10,
70,
250,
2500.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
18
Void
and
Diagonal
at
2-dim.
2
8
11
13
16
18
21
22
24
28 31
35
41
43
46
48
55
57
59
60
63
64
67 69 70
72 77
81
85
88
90
93
94
99
100
104
109
111
120 121
125 127
129 130
133
134
136
139 141
145 147
150
152
154 155
159
160 161
162 163
165
166
168
171 172
174
176 177
178
181
183
184 185 187 188 189
191 193 194
195
196
198 199
200
202 203 204
206 208
210 212 213
214
217
218 219
220 221
222 223 224 225
226 227
229
230 231
232
233
234 235
236
237
238 239
240 241 242 243
244 245
246 247
248
249
?
1
u
2
u
3
?
4
?
5
?
6
?
7
?
8
?
9
?
10
?
11
?
12
?
13
?
14
?
15
?
16 ?
17
u
18 ?
19
u
20
?
21
?
22
?
23
?
24
?
25
?
26
?
27
?
28
?
29
u
30 ?
31
?
32
u
33
?
34
?
35
u
36
?
37
?
38
?
39
u
40
?
41
?
42
u
43
?
44
?
45
?
46
?
47
?
48
?
49
u
50
?
51
?
52
u
53
?
54
?
55
?
56
u
57
?
58
?
59
?
60
u
61
u
62
?
63
u
64
u
65
?
66
?
67
?
68
u
69
u
70
?
71
u
72
u
73
u
74
?
75
?
76
u
77
u
78 u 79
u
80
u
81
?
82
?
83
u
84
?
85
u
86
?
87
?
88
u
89
u
90
u
91
u
92
u
93
?
94
?
95
u
96
?
97
u
98
?
99
u
100
u
101
?
102
u
103
u
104
u
105
u
106 u 107
u
108
u
109
u
110
u
111
?
112
?
113
u
114
u
115
u
116
u
117
u
118
?
119
u
120
u 121
u
122
u
123
u
124
u
125
u
126
u
127
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
16
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
18
24
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Gamma
\Gamma
\Gamma
28
\Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi30 \Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Gamma \Gamma
\Gamma 32
hhhhhhhhhhhhhhhhhhh
34
\Pi
\Pi
\Pi
hhhhhhhhhhhhhhhhhhh 35
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
\Gamma \Gamma
\Gamma
41
Z
Z
Z
Z
44
c c c
47
,
,\Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi
50
h
h
h
h
h
h
h
h
h
h
h
h
h
h
60
(((
63
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h \Xi \Xi
64
66
`` `` ``
\Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi
72
75
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
77
h
h
h
h
h
h
(
(
(
(
(
(
(
(
(
(
(
(
(
78
?
?
? \Gamma
\Gamma
\Gamma
81
hhhhhhhhhhhhhhhhhhh
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
85
87
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi \Gamma \Gamma \Gamma
91
h
h
h
h
е
е
95 hhhh
99
h
h
h
h
h
h
h
h
h
h
h
101
A A 102
P
P
P
P
P
h
h
h
h
h
104
hhhhhhhhhhhh\Xi \Xi
108
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
113
115
117
hhhhhhhhhhhhhh 119
((((( 121 L L L
124
L L L
``
``
`` 125
ееееее
(
(
(
(
(
(
(
(
(
(
(
(
(
126
E E E
128
hhhhhhhhhhhhhh h
h
h
133
135
Q Q L
L
L \Pi \Pi 136
138
139
140
h
h
h
h
h
141
hhhh 143
S
S
\Gamma \Gamma 145
E
E
E
\Delta \Delta \Delta
146
P P P
P P
P
P
P 148
\Delta
\Delta
\Delta \Pi \Pi \Pi
150 , , \Delta \Delta
151
X
X
X
X
X
X
X
\Gamma \Gamma \Gamma
153
((((((((
(
(
(
(
(
(
(
(
(
(
(
154
!
!
((((((((((((( (
(
(
(
(
(
(
(
(
(
(
(
(
(
156
ееее ! !
(
(
(
157
i
i
i
ii
i
i \Gamma \Gamma
159
hhhhhhhhhhhhhhh h
h
h
h
h
h
h
h
h
h
h
h
h
h
160
162 163
164
hhhhhhhh P
P
166
h
h
h
h
h
h
h
h
h
h
h
h
h
h
hhhhhhhhhhhhhhhhhhh 169
hhhhhhhhh P
P
P
h
h
h
h
h
h
h
170
172 \Pi
\Pi
\Pi
\Pi E
E
E
173
\Pi \Pi \Pi
175
h
h
h
h
h
h
''
''
177
\Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi
178
179
hhhhhhhh h
h
h
h
h
h
h
h
181
hhhhhhhh 183
''
''
h
h
h
h
h
h
h
PPP
PP 185
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h X X X
186
////////// е
е
е
е
е
е
е
е
189
190
((((((((((((((((( (
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
192
hh194
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
hhhhhhhhhhhhhhhhhhhhhhh 195
h
h
196
197
j j
(((((((( /
/
/
/
/
/
/
/
/
/
198
D D E
E
E
E 200
D
D
201
J J J L
L
L 202
Q Q 203
hhhhh 204
h h h
h
h
h
h
h
h
h
h
h
h
h
h
h
205
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi
\Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi \Pi
206 \Pi
\Pi
\Pi 207
@ @ J
J 208 @ @ 209
E E E
210 \Delta \Delta
211
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
((((((((((((((((( i i
212
((((((((((((((( i
i
i
i
i
214
215
X
X X
216
217
218
220
222
(
(
(
(
223
( (
h
h
h X X 224
P
P
P
P
P
( (
XXXXXX 225
226
(
(
(
(
(
(
(
(((((((((((((((( (
(
(
(
(
(
(
(
(
( 228
(((
(((((((( (
(
(
(
(
(
(
(
(
(
229
230 231
233
235
236
237
238 A A\Pi \Pi
239
hhhhhhhhhhhhhh h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
240
` `
`
`hhhhhh h
h
h
h
h
h
h
h
h
h
242
hhhhhhhhh `
`
`
`
h
h
h
h
h
243
ш
ш
ш
? ? ?
244 \Gamma
\Gamma
\Gamma ш ш ш
245
(((((( i i i 246i
i
i j j 247
E E 248
E E 249
49
52
56
59
63
64
69
75
80
82
89
91
92
94
97
98
102
106
110
112
115
117
120
122
125
127
129
131
133
134
135
137
139
141
142
143
144
147
149
151
152
154
156
159
161
162
165
166
167
168
170
171
172
173
175
176
177
178
179
180
181
183 184
187
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220221
222
223
224
225
226227
228
229
230
231
232233
234
235
236
237
238
239
240
241
242
243
244
245
246 247
248249
u
1
?
2
?
3
u
4
?
5
?
6
?
7
?
8
?
9
?
10
?
11
?
12
?
13
?
14
?
15
?
16
?
17
?
18
?
19
?
20
?
21
?
22
?
23
?
24
?
25
u 26
?
27
?
28
?
29
?
30
?
31
?
32
?
33
?
34
?
35
u
36
?
37
?
38 ?
39
?
40
?
41
?
42
u
43
?
44
?
45
?
46
?
47
u
48
?
49
?
50
u
51
?
52
?
53
u
54
u
55
u
56
?
57
?
58
u
59
u 60
?
61
u
62
u
63
?
64
?
65
u
66
u
67
?
68
?
69
u
70
?
71
u
72
?
73 u
74
u 75 u
76
u
77
u
78
u 79
u 80
u
81
u
82
u
83
u 84
u
85
u
86
u
87
u
88
u 89
?
90
u
91
u
92 u
93
u 94
u
95
u
96
u
97
u
98
u
99
u
100
u
101
u
102
u
103
u
104
u
105
u
106
u
107
u
108
u 109
u
110
u 111
u
112
u
113
u 114
u
115
u 116
u
117
u
118
u
119
u
120
u
121
u
122
u 123
u
124
u
125
u
126
u
127
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
l
l
l
l l
l
l
l
l
l l
l
l
l
l
l l
l
l
l
l
l
l \Gamma
\Gamma
\Gamma
76
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
80
l
l
l
l
l
l l @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
90
``
``
``
``
``
`` @ @
S
S
S
S
97
@
@
@
@ S
S
S
S
S 101
@
@
@
@
@
@
@
@
@
Z Z
Z
@
@
@
@
@
@
@
103
l
l
l
l
l
l
l @
@ @
@ @ @
105
b
b
b @
@
@
@ A A A
107
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
108
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
Z
Z
Z Z
@
@
@
@
@
@ @
@
@
@
@
@
@
111
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
114
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
115
e
e
e
e
e e
e
e
e
e
e
e
@
@
@
@
@
@
@
@
@
@
@
116
e
e
e
e
e
e
e e
e
e
e
e
e
e
e
e e
e
e
e
e
e
e
e
e @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
118
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@ l
l
l
l
l
120
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
123
l
l
l
l l
l
l
l
l
l @
@
@
@
@
@
@
@
@
@
124
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @ @
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
127
@
@
@
@
@
@
@
@
@
@
@
@
@
@ e
e
e
e e
e
e
e
e
e
e
e
e
128
e
e
e
e
e
e
e
e
e
e
e
e
e A A A A A A A A A A
A A A
129
@
@
@
@
@
@
@
@
@
@
@
@
@ @ @
@
@
@
@
@
@
@
@
@
@
@
131
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
133
e
e
e
e
e
e
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
134
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
135
J
J J
J J
P P
P P @
@
@
@
@
@
@
137
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
139
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
140
J
J
J
J J
J
J
J
J
J J
J
J
J
J
J J
J
J
J
J J J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
142
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
145
@
@
@
@
@
@
@
@
@
@
@
l
l
l l
l
l
l l
l
l
l l
l
146
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
147
c
c A
A
A
148 S
S
S S S A
A
A
c
c
149
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
T T
150
@
@
@
@
@
@
@
@
@
T
T e
e
e
e
e
e
e
e
e
e
e
151
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
152
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
153
Z
Z
Z
Z
Z
Z
Z
\Pi
\Pi@ @
@
@
@ @
@
154
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
@
@
@
@
@
@
@
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
c
155
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
156
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
157
S
S
S
S
\Pi \Pi \Pi \Pi
158 @
@
@
@S S S S
159
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
l l
161
@
@
@
l
l
l
l
l Q
Q
Q
162
e
e
e
e e
e
e
e
e @
@
@
@
@
@
@
@
164
@
@
@ @
@
@
@
@ @
@
@
@
@
@
@
@
165
@
@ @
@ @ @
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@ @
@
@
@
@
166
@
@
@
@
@
@
@
@
@
@ e
e
e
e
e
e
e
e
e
e
b
b
168
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
169
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
170
e
e
e
e
e
e
e
e
e
e
e @ @
@
@ @
@
@ @
@
@ @
171
c c e
e
e A A 173
@
@
@
@
@
@
@
c c
@
@
@ @
@
@
175
@
@
@
@ @
@
@
@
@
@
@
@
@ @ @
@
@
@ @ 176
l
l
l l
l
l
l l
l @
@
@
@
@
@
b
b
b
177
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
``
L L L L L L L L L L L L L L L L L L L L L L
178
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
``
``
``
``
``
``
`` ``
``
``
``
``
``
``
``
``
``
`` ``
``
179
@
@
@
@
@
@
@
@
@
@
@
``
``
``
`` ``
``
`` ``
``
`` ``
``
`` e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
180
@
@
@ @
@
@
@
@
e e e e
e @
@
@
@
@
@
@
@
@
@
@
181
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
182
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l \Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
\Gamma
183
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
184
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
185
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
186
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
l
l
l
l
187
@
@
@
@
@
@
@
@
@
@
@
l
l
l
l
l
l
l
l @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
188
@
@
@
@
@
@
l
l
l
l
l
l @
@
@
@
@
@
@
@
@
@
@
189
@
@
@
@
@ A A
@
@
@
@
190
``
``
``
``
``
`` `` A
A
A
@
@
@
@
@
191
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
193
``
``
``
``
``
``
`` @
@
@
@
@ @
@
@
@
@
@
@
@ @
@
@ @
@
@
@
@
@
@
@
@ 194
``
``
``
``
``
``
``
``
``
`` @
@
@
@
@
@
@
@
@ \Gamma \Gamma
195
l
l
l
l
l e
e
e
e
e
e
e
e A A A
196 @
@
@
@
@
@
@
@
@
@ e
e
e
e
e
e
l
l
l
l
l
197
c
c
c
c l
l
l
l
l
l
l
l
l
l @
@
@ @
@
@
198
c
c
c @
@
@
@
@
@ e
e e 199
e
e
e
e
e
e
e ``
``
``
``
``
``
``
200
@
@
@
@
@
@
@ e
e
e
e
e
e
e
201
@
@
@
@
@ A
A
A
A
P
P
P
P
202
J
J
J
J J
J
J
J J
J
J
J J
J
J
J J A
A
A
A
A
A
A
A
A
A
A
A
A
@
@
@
@
@
203
c
c
c c
c
c @
@
@
b
b
b
b
204
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
c
c
c
c
c
c
205
@
@
@
Q Q Q L L
206
l
l
l
l
l
l
l
l
l
l
l
l
l
l @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ e
e
e
e
e
e
e
e
e
208
l
l
l
l
l
l
l
l
l e
e
e
e
e
e
e
e
e
\Gamma \Gamma
209
XXXXXX J
J
J
J
J
\Gamma
\Gamma
\Gamma
210
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@ @ J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
X
X
X
X
X
X
211
c
c
B B
212
Z
Z
Z
Z
B
B @
@
@
@
213
b
b
b c
c
c
c
c
c
c
c
c l
l
l l
l
l
214 Q Q l
l
l
l
l
l @
@
@
@
215
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
217
@
@
@
@
@
@
@
@
@
@
@
@
@
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z \Gamma \Gamma
218
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
219
@ @
@
@ @
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@ S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
S
\Gamma
\Gamma
220
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
\Gamma \Gamma
221
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
222
S
S @
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
223
@ @ @
@
@
@
@
@
@
@
@ @ @
@
@
@
@
@
@
@
@
@
@
224
@
@ @
@
@ @
@
@
@ @
@
@ @
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
225
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ A A
226
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@ A A A
227
c
c
c
c
c
c
c
c
\Pi
\Pi
\Pie
e e
e
e e
e
e e
228
c
c
c
c
c
c
c
c
c
c
c
c
c
c
e
e
e
e
e
e
e
e
e @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
229
e
e @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
230
e
e @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
231
@
@
@
@ @
@
@
@ @
@
@
@
@
@ @ @
@
@
@
@
@
@
@ 232
e
e e
e e
e
e
e
e
e
e
e
e
e
e
@ @
@ @ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
233
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
234
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
235
@
@
@ @
@
@ @
@ @
l
l
l
l
l
l
l
l
236
@
@ @
@
@ @
@ @
@
l
l
l
l
l
l
l
l @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
237
e
e
e
e
e
e
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
238
@
@
@
@
@
@ e
e
e e
e
e
239
@ @
@ @
``
``
``
``
`` e
e
e
e
e
e
e
e
e
240
`` `` `` `` `` @
@
@
@ 241
l
l
l
l
l
l Z
Z
Z
Z
Z
242
@
@
@
@
@
@
l
l l
l l
l
243
b
b
b b
b
b
b
b
@
@
@
@ @
@
@
@
@ @
@
@
@
@
@ l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
244
@
@
@ @
@
@
@
@ b
b
b
b
b
b
b
b
245
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
246
S
S @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@ @
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
@
247
@
@
L L S
S S
248
@
@
@
@
@
@
@
@
@
@
S
S
S @
@ @
@
@
@
@
@
@
@
@
@
@
249
Number
of
cells=
250.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
19
Hyperrectangles
or
simplices?
.
Simplices
are
limited
to
low
dimensions
n
<
6
because
of
n!,
and
because
of
many
determinants
heavily
consuming
CPU
time
(for
integration
domain
being
simplex
it
is
slightly
better).
.
For
simplices
memory
consumption
is#
16n
Bytes/Cell,
this
is
a
serious
limitation.
.
For
hyperrectangles
memory
consumption
is#50Bytes/Cell
independently
of
n.
This
is
really
great!
How
it
is
done?
See
e-Print:
physics/0203033.
.
Experience
with
many
testing
distributions
has
shown
that
quite
often
hyperrectangles
provide
comparable
or
even
better
final
MC
efficiency
than
simplices.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
20
CPU
barrier:
one
quick
fix
is
found
Final
MC
efficiency
is
improved
essentially
by
the
increasing
No.
of
cellsN
c
.
CPU
time
of
exploration
T
#
nЧNc
ЧNsamp
whereNsamp
is
the
number
of
MC
events
used
in
exploration
of
each
newly
created
Cell.
Can
we
limitN
samp
somehow
in
order
to
increaseN
c
?
SOLUTION:
During
MC
exploration
of
a
new
cell
continuously
monitor
the
no.
of
accumulated
effectiveW
=
1
events:
Neff
=
(
#
wi)
2
#
w
2 i
and
stop
when
Neff
/nbin
>
25,
where
nbin
is
the
number
of
bins
in
each
histogram
used
to
estimate
the
best
division
direction/edge
and
parameter.
The
increase
ofNsamp
not
wasted
for
cells
in
which
integrand
is
varying
very
little.
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
21
Example
of
the
user
program
//
***
Initialization
***
double
MCwt;
TFDISTR
*Density1
=
new
TFDISTR(FunType);
//
Create
integrand
distr.
TPSEMAR
*PseRan
=
new
TPSEMAR();
//
Create
random
numb.
gener.
TFOAM
*FoamX
=
new
TFOAM("FoamX");
//
Create
Simulator
FoamX->SetkDim(
3);
//
Set
dimension,
h-rect.
FoamX->Initialize(PseRan,
Density1
);
//
Initialize
simulator
TFile
RootFile("rmain.root","RECREATE","histograms"); FoamX->Write("FoamX");
//Writing
Foam
obj.
on
the
disk
//
***
MC
Generation,
the
same
job
or
later
on
***
TFOAM
*FoamX
=
(TFOAM*)fileA.Get("FoamX");
//
find
object
FoamX->LinkCells();
//
restore
pointers
of
the
binary
tree
of
cells
TFHST
*hst_Wt
=
new
TFHST(0.0,1.25,
25);
//
Create
weight
histogram
double
*MCvect
=new
double[3];
//
Monte
Carlo
event
for(long
loop=0;
loop<1000000;
loop++){
MCwt
=
FoamX->MCgenerate(double
*MCvect);
//
Generate
MC
event
hst_Wt->Fill(MCwt,1.0);
//
Fill
weight
histogram
} //
***
Finalization
***
double
IntNorm,
Errel;
FoamX->Finalize(
IntNorm,
Errel);
//
Print
statistics,
get
normaliz.
double
MCresult,
MCerror,
AveWt,
WtMax,
Sigma;
FoamX->GetIntegMC(
MCresult,
MCerror);
//
get
MC
integral
double
eps
=
0.0005;
FoamX->GetWtParams(eps,
AveWt,
WtMax,
Sigma);
//
get
MC
wt
parameters
hst_Wt->Print();
//
Print
weight
histogram
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
22
Tests
of
Foam
at
low
dimensions
Functions
at
2-dimens.
Foam
1.01
Simpl.
H-Rect.
VEGAS
#a(x)
(diagonal
ridge)
0.93
0.93
0.86
0.03
#b(x)
(circular
ridge)
0.82
0.82
0.82
0.16
#c(x)
(edge
of
square)
0.57
1.00
1.00
0.53
Functions
at
3-dimens.
Foam
1.01
Simpl.
H-Rect.
VEGAS
#a(x)
(thin
diagonal)
0.67
0.74
0.66
0.002
#b(x)
(thin
sphere)
0.36
0.47
0.53
0.11
#c(x)
(surface
of
cube)
0.37
0.95
1.00
0.30
Results
from
Foam/MCell
are
for
5000
cells
(2500
active
cells)
and
cell
exploration
based
on
200
MC
events/cell.
Efficiencies
are >
/W
#
max
with
#=0.0005.
Keep
in
mind
that
efficiency
of
Foam
#w#/wmax
can
be
in
the
above
example
easily
increased
to
almost
100%
by
increasing
no
of
cells,
while
for
VEGAS
we
are
here
at
the
limiting
value!
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
23
Tests
of
Foam
at
higher
dimensions,
Camel
test-function
of
P.
Lepage,
normalized
to
one
nDim
kDim
nCalls
nCells
nSampl
w
#
max
/#w#
#/#w#
#statist.R
R
0
1
206192
1000
1000
0.99147
0.014752
1.043e-05
0.99999962
0
1
206192
1000
10000
0.99147
0.014752
1.043e-05
0.99999962
0
3
435112
1000
1000
0.50886
0.54033
0.000382
1.00017104
0
3
834094
1000
10000
0.50359
0.54674
0.000386
1.00056316
0
3
1015157
1000
33333
0.51091
0.54035
0.000382
0.99983999
0
3
2675820
10000
1000
0.72677
0.27504
0.000194
0.99995080
0
3
3333479
10000
10000
0.72200
0.27720
0.000196
1.00008994
0
3
3575366
10000
33333
0.72243
0.27786
0.000196
0.99997875
0
4
3825046
10000
1000
0.50363
0.51168
0.000361
1.00013082
0
4
6559430
10000
10000
0.50297
0.51001
0.000360
0.99960319
2
2
4493961
10000
1000
0.43076
0.63185
0.000446
1.00072564
2
2
9374351
10000
10000
0.44922
0.60669
0.000429
1.00013171
4
0
6642202
10000
1000
0.21029
1.19420
0.000844
1.00072248
4
0
12337748
10000
10000
0.20817
1.20067
0.000849
1.00020405
0
6
2311881
1000
3333
0.04199
2.12091
0.001499
0.99856206
0
6
12844256
1000
33333
0.03279
2.61028
0.001845
0.99799089
0
6
12737314
10000
3333
0.15385
1.15211
0.000814
1.00039754
0
6
42827237
10000
33333
0.14168
1.22627
0.000867
0.99954178
0
6
42808972
100000
1000
0.30910
0.71250
0.000503
0.99972833
0
6
92531875
100000
10000
0.30905
0.71423
0.000505
0.99985093
0
9
78325890
100000
1000
0.03718
1.64608
0.001163
0.99367339
0
9
353943409
100000
10000
0.05196
1.80538
0.001276
1.00196909
0
9
272162624
400000
1000
0.08490
1.30193
0.000920
1.00065580
0
9
924011087
400000
10000
0.08853
1.38579
0.000979
1.00052122
0
12
261911066
100000
3333
0
5.83954
0.004129
0.97304842
0
12
671460574
100000
10000
0.00640
3.85823
0.002728
0.98878698
0
12
913072065
400000
3333
0.01285
2.73991
0.001937
0.98688299
0
12
2117963809
400000
10000
0.01235
2.92642
0.002069
0.99301117
Efficiency
depends
mainly
on
number
of
cells
nCells.
Number
of
MC
trials
per
Cell
cannot
be
too
small.
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
0.2
0.4
0.6
0.8
1
S.
Jadach
June
26-th,
2002

ACAT2002,
Moscow
24
Conclusions
.
FOAM
is
a
versatile
adaptive
general
purpose
Monte
Carlo
simulator.
.
It
is
based
on
the
cellular
division
of
the
integration
domain.
.
Geometry
of
the
``foam
of
cells''
is
rather
simple,
following
the
rule
of
a
binary
split
(but
memory-efficient
coding
of
the
vertices
is
found).
.
The
rules
for
picking
up
next
cell
for
the
division
and
division
geometry
starts
to
be
relatively
sophisticated
(projection
on
edges
etc.)
.
FOAM
can
deal
with
peaked
distribution
up
to
10
dimensions,
with
todays
computers.
.
Latest
version
2.02
in
C++
and
f77
to
appear
in
in
Comp.Phys.Commun.,
available
from
the
author.
.
First
``real-life''
applications:
ISR
and
beamstrahlung
in
KKMC.
Looking
for
more
``killer-aps''!
S.
Jadach
June
26-th,
2002