Benoît Combès

José Braga

Francis Thackeray

Sylvain Prima

3D automated quantification of asymmetries on fossil endocasts

Over the last 15 years computed tomography (CT) has become a common way to obtain high resolution three-dimensional images of cranial endocast of hominids. Among the different features that can be seen on such endocasts, of key interest are their shape asymmetries. In particular, protrusions of the frontal and occipital lobes, as well as differences in their width, have been typically observed in modern humans' brains. These have been often hypothesized to be linked to functional specialization, and especially language and handedness. The imprints of these protrusions on the inner surface of the skull are called the petalia. There is a lack of automated, reproducible and objective methods to quantify these protrusions and to assess (for instance) whether they are present in species other than Homo sapiens.

We propose a new method for the automated quantification of 3D endocranial shape asymmetries. We mathematically define the symmetry plane of the endocast as the 3D plane which best superposes the "right" and "left" sides of the endocranial surface. Then, we compute a 3D pointwise deformation field between the two sides of the endocast, allowing to match homologous points, and to assess their relative spatial position. The analysis of this 3D deformation field allows quantifying the shape asymmetries everywhere on the endocast.

We illustrate our method on the endocast of Sts 5 (Mrs. Ples, Australopithecus africanus) whose very high resolution CT scan has been segmented using ITK-SNAP. The results suggest an opposite shape asymmetry in the fronto-temporal and occipital regions.

This abstract is part of the symposium entitled "Computational methods for the automated analysis of virtual hominid endocasts", organized by Sylvain Prima, Gérard Subsol and José Braga.

This research supported by the French Institute for Research in Computer Science and Control (INRIA). Grant: 3D-MORPHINE (Collaborative Research Initiative).


Gergely Nagy

Dorthe Posselt

László Kovács

Jens Kai Holm

Milán Szabó

Bettina Ughy

László Rosta

Judith Peters

Peter Timmins

Győző Garab

Gyęzę Garab

Gyęzę Garab

Reversible membrane-reorganizations during photosynthesis in vivo -revealed

Keywords: Neutron scattering reveals membrane-reorganizations during photosynthesis in vivo chloroplast thylakoid membranes, cyanobacteria, diatom, light-induced reorganizations, membrane ultrastructure, SANS CD, circular dichroism, DCMU, (3-(3,4-dichlorophenyl)-1,1dimethylurea), EM, electron microscopy, FCPs, fucoxanthin-chlorophyll proteins, LHCII, main light harvesting complex of PSII, PMS, N-methyl phenazonium methosulphate, PSI, photosystem I, PSII, photosystem II, Q, scattering vector, RD, spatially averaged repeat distance, SANS, small-angle neutron scattering

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction:

In order to increase the efficiency of light capturing, most photosynthetic organisms have evolved highly organized multilamellar membrane systems. They also exhibit remarkable structural and functional flexibility, which enables these organisms to carry out short term adaptations and long term acclimations in response to changes in environmental conditions [START_REF] Anderson | The dynamic photosynthetic membrane and regulation of solar-energy conversion[END_REF][START_REF] Allen | State transitions -a question of balance[END_REF][START_REF] Kargul | Photosynthetic acclimation: structural reorganisation of light harvesting antenna -role of redox-dependent phosphorylation of major and minor chlorophyll a/b binding proteins[END_REF][START_REF] Horton | Regulation of light harvesting in green plants[END_REF][START_REF] Mullineaux | Mobility of photosynthetic complexes in thylakoid membranes[END_REF][START_REF] Eberhard | The dynamics of photosynthesis[END_REF]. Our knowledge concerning the molecular mechanisms of photosynthesis has advanced greatly in the past two decades, owing to the availability of high resolution structural information of the protein components and their supercomplexes as well as detailed information from sophisticated spectroscopic techniques [START_REF] Renger | The light reactions of photosynthesis[END_REF]. In contrast, much less is known about the self-assembly and regulation of membrane ultrastructures under different environmental conditions.

To obtain detailed and accurate information on the membrane ultrastructure of photosynthetic organisms and their structural flexibilities during photosynthesis, noninvasive techniques are required, such as neutron scattering, which offers unique structural information on complex membrane systems under physiological conditions [8;9]. The neutron scattering length is very different for hydrogen and deuterium, thus allowing for systematic contrast variation in an aqueous environment by varying the H 2 O/D 2 O ratio in the suspension medium [10;11]. Depending on this ratio we can highlight protein and/or lipid parts of complex biological membrane systems. While interatomic distances are determined using diffraction methods, small-angle neutron scattering (SANS) can be used to determine the repeat distances in multilamellar membrane systems with long-range order. Accordingly, recording the scattered intensity as a function of the scattering vector, Q, a Bragg peak positioned at Q* determines a spatially averaged repeat distance (RD), characteristic of the entire statistical population: RD= 2ʌ/Q*.

The membrane ultrastructure of photosynthetic organisms depends largely on its composition and on the structure and arrangement of the integral and membraneassociated protein complexes. In oxygenic photosynthetic organisms, the initial steps of the conversion of light energy into chemical energy occur in flattened vesicular bilayer structures, called the thylakoid membranes. These membranes separate the inner aqueous phase, the lumen, and the outer aqueous phase. The membranes contain two photochemical systems: photosystem I (PSI), responsible for the production of NADPH, carrying the reducing power, and photosystem II (PSII), which catalyses the oxidation of water. The thylakoid membranes also embed the cytochrome b6/f complex and the ATP synthase. The energy supply for photosynthesis is provided mainly by extended arrays of accessory light harvesting antenna complexes, which increase the effective absorbance cross sections of the photosystems. These complexes are either integral membrane proteins, as in higher plants and most algal cells, including the diatoms, or large external protein aggregates, the phycobilisomes, as in cyanobacteria and red algae. The presence of external proteins anchored to the membrane and polypeptide sections protruding from the thylakoid lamellae toward the outer aqueous phase poses restrictions for the distances between adjacent thylakoid membranes [START_REF] Dekker | Supramolecular organization of thylakoid membrane proteins in green plants[END_REF], thus limiting the packing density of membranes and their possible minimum RDs. Regarding the membrane ultrastructure and In this work we performed SANS experiments on three basically different classes of oxygenic photosynthetic organisms: i) a cyanobacterium -these prokaryotic organisms are the progenitors of chloroplasts in green plants, ii) a diatom species -representative of the major group of algae, which, due to their specific lifecycle, play an essential role in the regulation of atmospheric CO 2 concentration, and iii) granal chloroplasts isolated from a higher plant -representing the most abundant and one of the most complex membrane systems in the Biosphere. By using SANS we were able to study photosynthetic membrane ultrastructures of these species in vivo, determine the membrane RDs and in particular, their time-resolved light-induced reversible changes.

Experimental: Alga cultures, growth conditions and sample preparation

The PAL mutant cells of Synechocystis PCC 6803 were grown photoautotrophically in BG 11 medium [START_REF] Wilson | A soluble carotenoid protein involved in phycobilisome-related energy dissipation in cyanobacteria[END_REF] supplemented with 5 mM HEPES NaOH (pH 7.5) at 30 ºC under continuous illumination at a photon flux density of 30 μmol photons m -2 s -1 . Phaeodactylum tricornutum (1090-1a, obtained from the Culture Collection of Algae, Göttingen (SAG)) was cultivated as described in [START_REF] Lepetit | Spectroscopic and molecular characterization of the oligomeric antenna of the diatom Phaeodactylum tricornutum[END_REF] at a photon flux density of 40 μmol photons m -2 s -1 with light/dark periods of 16h/8h at 19 °C. Cells were harvested from the logarithmic (or exponential) growth phase, by centrifugation (5000 g, 5 min) and resuspended for SANS measurements in ~95% (v/v) D 2 O-containing culture medium to a chlorophyll content of 200-500 ȝg/ml. Thylakoid membranes were freshly isolated from market spinach. Leaves, after main ribs being removed, were homogenized in ice cold grinding medium containing 20 mM Tricine (pH 7.6), 0.4 M Sorbitol, 10 mM MgCl 2 , 10 mM KCl and filtered with 6 layers of medical gauze pads. Remaining debris was removed by centrifugation (200 g, 2 min). The supernatant was centrifuged for 5 min at 4000 g; the pellet was resuspended in osmotic shock medium containing 20 mM Tricine (pH 7.6), 5 mM MgCl 2 and 5 mM KCl. This was then centrifuged for 5 min at 7000 g. The pellet obtained was washed in D 2 O-containing grinding medium (pD 7.6) and centrifuged for 5 min at 7000 g. Thylakoid membranes resuspended in the same medium to a chlorophyll concentration of 1-2 mg/ml were stored at 4 °C and used within 4 h. Aliquots from the stock solutions were supplemented with 100 ȝM N-methyl phenazonium methosulphate (PMS) to catalyse cyclic electron transport around PSI or with 1 mM methylviologen for providing electron acceptor for the whole chain, linear electron transport; the uncouplers, nigericin and NH 4 Cl were used at 2.5 ȝM and 4 mM concentrations, respectively. For SANS measurements, isolated thylakoid membranes were oriented with their membrane normal approximately parallel to the applied field in an electromagnet of 1.5 T field strength with the field vector perpendicular to the neutron beam. D 2 O was purchased from Euriso-top, all other chemicals were obtained from Sigma-Aldrich. ). Sample suspensions filled in 1 mm quartz cuvettes were mounted in a temperature controlled sample holder placed in the neutron beam, defined by a 10 mm × 6.5 mm size aperture in front of the sample. The sample temperature was maintained at 15 ºC. Neutrons, scattered from the sample were detected with the aid of a position sensitive 3 He multidetector with 128×128 pixels, each pixel having a size of 8×8 mm 2 . The sample-to-detector distance was set to 2.45 m or 8 m; the corresponding collimation distances, which determine the beam divergence, were 2.8 m and 8 m, respectively. With these instrument settings we could cover a Q-range of 0.008 -0.2 Å -1 . Integration time of the data acquisition was varied between 1 s and 5 min; the data storage time was ~1 s. Pilot experiments on the Yellow Submarine SANS instrument at the Budapest Research Reactor were carried out as described in [15;16]. Additional experiments were also performed at SANS II, Paul Scherrer Institute, Switzerland.

SANS

Data Treatment

Data reduction of two dimensional scattering data (example shown in Supplementary Figure 1) recorded during the experiments was performed by the Graphical Reduction and Analysis SANS Program for Matlab TM (GRASP), developed by Dr. Charles Dewhurst at the ILL. The data counts for each pixel, n , and errors, n , were normalised to the number of beam monitor counts and multiplied by a constant (standard monitorset to be 10 7 ). Correction for detector efficiency and absolute calibration was performed by normalisation to the scattering from a 1 mm thick H 2 O sample. Buffer and sample holder scattering together with instrument background were measured and subtracted from the sample scattering taking the transmissions of sample and buffer/sample holder into account. The 2D scattering signal thus obtained was radially averaged along circles around the beam centre position for unoriented samples. In case of oriented samples, the data were radially averaged in 2 sectors centred around each opposite Bragg peak and with 45º opening angles.

Structural information was deduced from the radially averaged scattering curves as follows. For plant thylakoid membranes and for Phaeodactylum tricornutum at low [0.023 Å -1 , 0.053 Å -1 ] Q, the scattering profile was fitted with the sum of a Gaussian and a power function. For the PAL mutant of Synechocystis PCC 6803 the scattering curve was fitted with the sum of two independent Gaussians and a power function. Peak positions of the Gaussians, Q*, were used for determining repeat distances of the different thylakoid membrane assemblies (RD= 2ʌ/Q*).

Results and Discussion:

The thylakoid membranes in most cyanobacteria are arranged into concentric or radial arrays [17]. The packing density of membranes in these organisms is determined by the phycobilisomes: the distance between two adjacent membranes (the interthylakoidal A c c e p t e d M a n u s c r i p t space) was found to be 460 and 40 Å, in the presence and absence of phycobilisomes, respectively -determined by electron microscopy on the wild type and a mutant unicellular cyanobacterium Synechocystis PCC 6803 [START_REF] Olive | Ultrastructure and light adaptation of phycobilisome mutants of Synechocystis PCC 6803[END_REF]. In the wild type cells no Bragg peak could be discerned in the Q-range corresponding to a RD between 550 and 600 Å, which would be expected with the above cited interthylakoidal space and a thylakoidal contribution of about 125 Å [cf. [START_REF] Daum | Arrangement of photosystem II and ATP synthase in chloroplast membranes of spinach and pea[END_REF], discussed below]. This is most probably because of strong forward scattering of the whole cells and the smearing effect of the hemispherically shaped membrane-anchored phycobilisomes. In contrast, the PAL mutant [START_REF] Ajlani | Construction and characterization of a phycobiliprotein-less mutant of Synechocystis sp. PCC6803[END_REF] of Synechocystis PCC 6803, which is devoid of phycobilisomes, exhibited a reasonably sharp Bragg peak at 0.032 Å -1 (Figure 1A), corresponding to a RD of ~ 190 Å (Table 1). The measured RD values, representing statistically averaged values, are somewhat higher than expected based on electron microscopy data: a thylakoid vesicle thickness of 125 Å plus the 40 Å interthylakoidal space [START_REF] Olive | Ultrastructure and light adaptation of phycobilisome mutants of Synechocystis PCC 6803[END_REF].

In diatoms the chloroplast thylakoid membranes are loosely appressed and organised into groups of three [21;22]. Each of these membranes contains both PSII and PSI, along with their common light harvesting antenna complexes, the fucoxanthin-chlorophyll proteins (FCPs). In the diatom Phaeodactylum tricornutum, we obtain a RD of ~170 Å (Table 1). This RD evidently requires a tight packing of membranes -given the even distribution of PSII, PSI and FCPs [START_REF] Wilhelm | The regulation of carbon and nutrient assimilation in diatoms is significantly different from green algae[END_REF]. In plants, such an arrangement of PSII and PSI complexes would require a somewhat larger RD of ~185 Å: PSI protrudes about 40 Å while both PSII and its main light harvesting complexes (LHCII) are extended by about 20 Å into the interthylakoidal space; the membrane thicknesses are ~40 Å each, and the lumenal spacing is ~45 Å [12;19]. In diatoms, however, FCPs possess considerably smaller loop segments [21;23] than LHCII -thus allowing a smaller interthylakoidal space and smaller RD. Concerning the location of the ATP synthase in diatoms, with its estimated large, ~140 Å protrusion [START_REF] Stock | Molecular architecture of the rotary motor in ATP synthase[END_REF], it is clear that this enzyme can only be accommodated in the 'end' membrane, i.e. on the outer surfaces of the groups of three thylakoid membranes. This implies that the thylakoid in the middle must be energetically coupled, evidently via interconnected lumenal spaces and contiguous bilayer membranes, to the two end membranes.

In the chloroplasts of higher plants, cylindrical stacks of granum thylakoids, with typical diameters of 300-600 nm and containing 5-20 thylakoids are interconnected by nonappressed, so-called stroma thylakoid membranes [START_REF] Mustárdy | Granum revisited. A three-dimensional modelwhere things fall into place[END_REF]. With this lateral heterogeneity, there are two RDs in the system, corresponding to the grana stacks and stroma lamellae, respectively. In grana, which in the stacked region contain PSII and LHCII but no PSI, RD can be small indeed, a RD grana of 157 Å (with 45 Å lumenal and 32 Å interthylakoidal space) has recently been determined by cryo-EM for spinach chloroplasts [START_REF] Daum | Arrangement of photosystem II and ATP synthase in chloroplast membranes of spinach and pea[END_REF]. RD grana was found to be 167 Å in dark-adapted Arabidopsis leaves after cryo-immobilization and freeze-substitution (H. Kirchhoff and Z. Reich, personal communication). In contrast, RD stroma must be considerably larger, due to the presence of PSI and the ATP synthase in these membrane sections. Indeed, in freshly isolated intact spinach thylakoids we find well defined Bragg peaks corresponding to RDs between 285-300 Å (Figure 1C, Table 1). These RDs can accommodate a ~125 Å thick thylakoid vesicle and allow 160 Å protrusions between the lamellae. For reasons probably related to symmetry and/or lack of contrast, the first order Bragg peak of the multilamellar grana stacks is missing -under all experimental conditions tested. (For theoretical treatment of the small angle scattering of granal thylakoid membranes, see [START_REF] Kirkensgaard | Simulation of small-angle X-ray scattering from thylakoid membranes[END_REF].) Instead, as will be shown elsewhere, grana, as well as PSII membrane-pairs devoid of the interconnecting stroma thylakoids, i.e. pairs of adjacent stacked membranes isolated from granal chloroplasts, display characteristic scattering in the Q-range between 0.065 and 0.07 Å -1 .

In order to investigate if these membrane ultrastructures are stable under different conditions and in particular during the photosynthetic functions, we carried out time resolved SANS experiments. These measurements on the PAL mutant of Synechocystis PCC 6803 revealed, to our knowledge for the first time, rapid light-induced RD changes of the thylakoid membranes in living cyanobacterial cells (Figure 1A). The magnitude of these changes, which probably originate from variations in the surface charges during photosynthesis, is rather small (~ 10 Å), rendering them almost certainly undetectable by EM. It is also noteworthy that the changes were fully reversible in the dark. This phase was rather slow, which suggests the existence of two states, a light adapted state and a dark adapted state of the thylakoid membrane RDs. Similar membrane reorganizations are observed in Phaeodactylum tricornutum cells (Figure 1B), where the full reversibility is also slow (30-60 min), similar to the relaxation after the photoprotective nonphotochemical quenching of the fluorescence in the antenna in the dark [27;28], and to the light-induced reorganizations in the chiral macroorganization of the pigment system detected by CD spectroscopy [START_REF] Szabó | Structurally flexible macro-organization of the pigment-protein complexes of the diatom Phaeodactylum tricornutum[END_REF]. The structural flexibility of diatoms might be related to their well known ability to survive large fluctuations in light intensity in mixing waters [30;31]. With regard to higher plants, our studies reveal unexpectedly high structural flexibility of stroma thylakoids. Fully reversible light-induced reorganizations, observable already in 2-dimensional scattering profiles (Supplementary Figure 1), could be recorded with a time-resolution of several seconds, which affected both RD and the degree of the lamellar order -manifested in shifted peak positions and broadened and diminished Bragg peaks, respectively (Figure 1C). It is interesting to note that the lightinduced changes in the RD were smaller when whole chain, instead of PSI cyclic electron transport, was operating, i.e. when PMS was replaced with methylviologen (Supplementary Figure 2). These reorganizations in plant thylakoid membranes closely resemble the light-induced shrinking of thylakoid membranes, detected earlier by electron microscopy as well as by light scattering, and which has been shown to be driven by transmembrane ǻpH generated during photosynthesis [START_REF] Murakami | Protonation and chloroplast membrane structure[END_REF]. In perfect agreement with these data, we show that uncouplers eliminate the light-induced RD changes, a shrinkage, in isolated plant thylakoid membranes (Supplementary Figure 3A andB). In contrast, NH [START_REF] Horton | Regulation of light harvesting in green plants[END_REF] Cl had no significant effect on the light-induced RD change, a swelling, in the diatom P. tricornutum (Supplementary Figure 3C andD), showing that the light-induced transmembrane ǻpH in the two systems do not play the same role in the membrane reorganizations. While the mechanism of the light-induced membrane reorganizations in diatoms remains to be explored, it is to be noted that the macro-organization of membranes, the roles of transmembrane proton gradients generated upon illumination and via chlororespiration in the dark as well as some details of the regulatory mechanisms of non-photochemical quenching display significant differences in the two systems [33;34]. In summary, in the past decades a wealth of information has accumulated on different reorganizations which are part of the multilevel regulatory mechanisms of photosynthetic organisms and which affect the overall membrane organization [1-6;32-38]. As demonstrated in this paper, SANS allows the determination of RDs of the membrane ultrastructure in different photosynthetic organisms and the monitoring of their timeresolved reorganizations during photosynthesis, information hitherto not available. This technique is thus suitable for the fast and accurate determination of repeat distances on the entire population of multilamellar, inherently heterogeneous biological membrane systems in vivo. Our data provide clear evidence for the occurrence of small but well discernible membrane reorganizations during photosynthesis, which appear to be linked with basic regulatory mechanisms. Cells and isolated thylakoid membranes were suspended in D 2 O-containing reaction media. The standard errors characterize the uncertainty of the peak positions calculated from the scattering curves fitted with the sum of a Gaussian and a power function for the corresponding section of SANS (cf. Figure 1). The data on the PAL mutant and P. tricornutum were obtained from two different batches; variations of RD between independent measurements on the same batch were smaller than 1.5%. Independent measurements on the same batch of isolated spinach thylakoids under the same conditions yielded essentially identical values but during storage RD tended to increase by several percent.

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t regulatory functions in different classes of photosynthetic organisms nature displays astounding variations in various organisms from primitive bacteria to higher plants.

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p tNeutron scattering experiments were performed on the D22 small angle neutron scattering instrument at the Institut Laue-Langevin (ILL) in Grenoble, France, where a //www.ill.eu/instruments-support/instruments-groups/instruments/d22/). Neutrons thermalized in a cold source were monochromatized by a mechanical velocity selector to obtain a neutron wavelength (Ȝ) of 6

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t the Hungarian Scientific Research Fund/National Office for Research and Technology [No. 80345] grants to G.G., National Office for Research and Technology [NAP-VENEUS05] grant to L.R. and Bourse du Gouvernement Français to G.N.; D.P. thanks the Danish Centre for the use of Synchrotron X-ray and Neutron facilities (DANSCATT) for financial support. Biochemical Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law. © 2011 The Authors Journal compilation © 2011 Portland Press Limited

A c c e

  p t e d M a n u s c r i p t A c c e p t e d M a n u s c r i p t rearrangements in chloroplast thylakoid membranes revealed by differential scanning calorimetry and circular dichroism spectroscopy. Thermo-optic effect. Biochemistry 42, 11272-11280 Biochemical Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t Licenced copy. Copying is not permitted, except with prior permission and as allowed by law. © 2011 The Authors Journal compilation © 2011 Portland Press Limited

Biochemical

  Journal Immediate Publication. Published on 08 Apr 2011 as manuscript BJ20110180 THIS IS NOT THE VERSION OF RECORD -see doi:10.1042/BJ20110180 A c c e p t e d M a n u s c r i p t

Figure 1 .Figure 1 Biochemical

 11 Figure 1. Effect of illumination on the SANS profiles of thylakoid membranes in living cyanobacterial cells (A), and diatoms (B) and in suspensions of isolated plant thylakoid membranes (C). (A) the PAL mutant of Synechocystis PCC 6803, (B) the diatom Phaeodactylum tricornutum, and (C) isolated spinach thylakoid membranes -the SANS signal of stroma lamellae. Insets, time courses of the light-induced variations in the repeat distances, calculated from the first order Bragg peaks, and their dark recovery phases. The additional peaks seen at Q values at around 0.048 Å -1 (A) and 0.065 Å -1 (B) are proposed to originate from paired membranes of adjacent thylakoids. The samples were illuminated for different time periods with white light of 2000 (A), 1200 (B) and 1700 (C) μmol photons m -2 s -1 photon flux densities, as indicated by the light (light on) and dark (light off) horizontal bars.

Table 1 . Repeat distance (RD) values of dark adapted thylakoid membranes in living cyanobacterial (Synechocystis) and eukaryotic algal cells (the diatom P. tricornutum), and of the stroma lamellae of isolated intact spinach thylakoid membranes.

 1

	Tables
	Organism	Calculated RD
	PAL mutant of Synechocystis PCC 6803
	batch 1	195 ± 1 Å
	batch 2	180 ± 1 Å
	Phaeodactylum tricornutum
	batch 1	169 ± 1 Å
	batch 2	171 ± 1 Å
	Spinach -stroma lamellae of isolated intact	301 ± 1 Å (largest)
	thylakoids	286 ± 1 Å (smallest)

Licenced copy. Copying is not permitted, except with prior permission and as allowed by law.© 2011 The Authors Journal compilation © 2011 Portland Press Limited

© 2011 The Authors Journal compilation © 2011 Portland Press Limited

Acknowledgements

We would like to thank the Institut Laue-Langevin (Grenoble, France) for providing us beamtime for the experiments. We are indebted to Dr. Ghada Ajlani (CEA, Saclay) for providing us the PAL mutant of Synechocystis PCC 6803 and for critical reading of a version of this manuscript and to Dr. Charles Dewhurst, Dr. Philip Callow, Dr. Lionel Porcar and Peter Cross (ILL, Grenoble) for helping us in configuring of the experiments and advice on data treatment. We also wish to thank Kasper H. Swiatek (Roskilde University) and Dr. Eszter Rétfalvi (RISP, Budapest) for participating in some of the experiments and Dr. Zoltán Gombos (BRC, Szeged) for helpful discussions.

Funding:

This work was supported by the Marie Curie Initial Training Network 'HARVEST' sponsored by the 7 th Framework Program of the European Union [No. 238017] and by


Roman Gula
email: rgula@miiz.waw.pl

Jörn Theuerkauf

Sophie Rouys
email: sophierouys@lagoon.nc

Andrew Legault
email: alegault@utas.edu.au

An audio/video surveillance system for wildlife

Keywords: Methods, Video surveillance, Nest monitoring, Digital video

published or not. The documents may come

Introduction

Improvements in digital technology over the last decade have facilitated the use of video for studying wildlife. Camera systems featuring motion sensors, time lapse and continuous recording have been widely used to document the presence and behaviour of animals at nests, trap sites and wildlife passages [START_REF] Reif | Using time-lapse digital recording for a nesting study of birds of prey[END_REF][START_REF] Kleist | Using video surveillance to estimate wildlife use of a highway underpass[END_REF][START_REF] Huckschlag | Development of a digital infrared video camera system for recording and remote capturing[END_REF][START_REF] Scheibe | Long-term automatic video recording as a tool for analysing the time patterns of utilisation of predefined location by wild animals[END_REF]). Several systems have been developed and tested for continuous monitoring of bird nests [START_REF] Currie | A new technique for filming prey delivered to nestlings, making minimal alterations to the nest box[END_REF][START_REF] Dearborn | Video documentation of a brown-headed cowbird nestling ejecting an indigo bunting nestling from the nest[END_REF][START_REF] Delaney | An infrared video camera system for monitoring diurnal and nocturnal raptors[END_REF][START_REF] Margalida | A portable system for continuous monitoring of bird nests using digital video recorders[END_REF][START_REF] Lin | The diet of fairy pitta Pitta nympha nestlings in Taiwan as revealed by videotaping[END_REF]Pierce and Pobprasert 2007;[START_REF] Colombelli-Négrel | A new audio-visual technique for effectively monitoring nest predation and the behaviour of nesting birds[END_REF].

The impact of introduced wildlife on native birds is presumed in many cases, but rarely documented and quantified [START_REF] Towns | Have the harmful effects of introduced rats on islands been exaggerated?[END_REF]. Accordingly, rats have been assumed to prey on broods of endemic birds in New Caledonia [START_REF] Warner | The present status of kagu, Rhynochetos jubatus, on New Caledonia[END_REF][START_REF] Létocart | Spatial organization and breeding of Kagu Rhynochetos jubatus in Rivière Bleue Park, New Caledonia[END_REF]BirdLife International 2009a, b). Our goal was to develop a video surveillance system that allowed continuous monitoring of bird nests in order to: (1) identify nest predators, (2) quantify predation and (3) study the behaviour of nesting birds. In this paper, we present 7 years of experience with an audio/video recording system that we developed and used to monitor broods of four endemic bird species of New Caledonia.

Study area and methods

The study areas were located in rainforests of Parc Provincial de la Rivière Bleue (22°3-12′S, 166°33-46′ E) and Parc des Grandes Fougères (21°37-38′ S, 165°45-46′ E) in New Caledonia (southwest Pacific). The climate is tropical oceanic, with mean annual temperatures ranging from 22°C to 24°C (ORSTOM 1981). Annual mean rainfall is 2,500-3,500 mm (Parc Provincial de la Rivière Bleue) and 1,500-2,000 mm (Parc des Grandes Fougères). Black Rats (Rattus rattus), Pacific Rats (Rattus exulans) and Feral Cats (Felis catus) inhabit both study areas [START_REF] Rouys | Factors determining the distribution of introduced mammals in nature reserves of the southern province, New Caledonia[END_REF], and are considered as potential predators of the studied bird species.

The video monitoring system consisted of a commercial infrared illuminator surveillance camera (Sony 1/3′′ CCD image sensor), and an Electret mini microphone with builtin SMD amplifier (Henri Electronic, Germany), connected to a recording device via a 6.4-mm multicore cable (Fig. 1). The transmission cable consisted of a 3-mm coaxial cable for the video signal, a 2.2-mm coaxial cable for the audio signal and two 2-mm (0.75 mm 2 ) cables to power the camera and microphone. From 2002 to 2007, we used video cassette recorders (Panasonic NV-HV55 VCRs) with standard 4-h VHS tapes set to record for 12 h on extended play. We powered the systems with 25-kg deep cycle, leadacid batteries with a storage capacity of 100 Ah. In 2007, we replaced VCRs with portable DVRs (Digital Video Recorders), as described by Pierce and Pobprasert (2007). Since then, we have used both Archos™ 504 DVRs (with 80 GB hard drives) and Archos 700 DVRs (with 100 GB hard drives).

All cameras were equipped with 12 infrared light emitting diodes (LEDs) for night vision. Surveillance cameras were waterproof to 1 m, and dust tight (International Protection Rating IP=67), therefore they did not require any additional cover. We put the microphone into a plastic bag, and taped it under the camera body. Initially, we connected the camera and microphone to the transmission cable using commercial video and audio connectors. The system was easy to set up, however connections tended to fail when left at the nest for long periods. Consequently, we dismantled the connectors, soldered the wires from the camera and microphone directly to the transmission cable and sealed the soldered connections with 3M™ Temflex™ Rubber Splicing Tape. We connected the transmission cable to the recorder using a dedicated Fig. 1 The components and wiring audio/video surveillance system Archos A/V cable. Although we initially used the RCA connectors supplied with the Archos A/V cable (as shown in Fig. 1), we eventually removed them and soldered the mono audio and video wires directly to the transmission cable to prevent connection failures. Our microphone recorded in mono, so we also removed the second RCA plug, and covered any exposed wiring with splicing tape. In other environments, it may be possible to use this cable without modification. This would allow the researcher to use the Archos A/V cable to playback audio on a stereo system, or video on an external monitor or TV. We soldered the transmission cable to the power cables, which led to clips connected to the battery. The VCRs were powered from the battery through a 12/220 V transformer. The DVRs were powered through an Archos car lighter adapter connected to a female lighter socket with power cables clipped to the battery (Fig. 1).

To monitor ground nests, we attached the camera to a 1-m fibreglass stick driven into the soil. For nests in tree hollows, we attached the camera to the tree trunk. When we mounted the camera 20-150 cm from the bottom of the nest, we used a camera with a 3.6 mm lens, and when we mounted the camera 100-300 cm from the nest bottom, we used a camera with a 6.0 mm lens. Due to the length of the transmission cable, we positioned the recorders within 50 m of the nests. However, this type of cable is technically specified to transmit sound and video up to about 80 m, without requiring additional amplification. We attached the cable to branches at a height of approximately 1 m, in order to minimise damage from rats. We put each recorder in a plastic storage box (dimensions: 40×60×20 cm for VCRs, 20×30×10 cm for DVRs), and placed the box on top of the batteries, which remained on the ground. We drilled a 2-cm hole in the bottom of each box to pass the cables through, which also provided ventilation. We used a waterproof tarp to cover the batteries and the box that contained the recorder.

We watched video cassettes at 36 times speed on a TV, and digital video recordings at 24 times speed on a computer. Whenever we noticed an event that we were interested in (arrival of predators, entrance or departure of parents, provision of food, tending of young, nest preparation and social interactions), we rewound the video, watched the event at normal speed and recorded its starting time and duration.

Results

Between 2002 and 2009, we used seven audio/video surveillance systems for monitoring the nests of four endemic species in New Caledonia: Kagu Rhynochetos jubatus, New Caledonian Parakeet Cyanoramphus saisseti, Horned Parakeet Eunymphicus cornutus and New Caledonian Whistler Pachycephala caledonica (Table 1). In total, we recorded nesting birds for over 22,000 h, and the longest period that we recorded continuously was 58 days. The maximum length of time that we kept a camera at a nest was 7 months (including time before and after breeding). Over this period, we checked weekly if birds were coming to the nest. After the female laid the first egg, we recorded the nest for another 100 days, with the only interruptions being due to poor connections or battery failures.

While watching the recordings of Kagu broods, we were able to recognise individual Kagus that we had marked with metal and colour bands, which made it possible to quantify the different behaviours of nesting Kagus. Also, we could usually identify the type of food that adult Kagus fed their chicks (i.e., earthworms and insects). Although we observed rats visiting the nests, we never recorded any predation (Table 1).

At nests of New Caledonian Parakeets and Horned Parakeets, we used video and sound recordings to differentiate between the behaviour of females, males and chicks (Table 1). In some cases we could recognise individual parakeets, which led to the discovery that two male New Caledonian Parakeets were attending the same nest, and feeding the chicks. Male parakeets often stayed outside the nest, rather than entering it, yet on many occasions we were still able to detect their presence by their recorded vocalisations. We also observed visits of potential nest predators, like rats and lizards, and their interactions with nesting females, but only recorded predation once (Table 1). Our original recording system, equipped with a VCR, required us to change tapes every 12 h, and to change the battery every 36 h. In practice, we were able to record for a maximum of 4.5 days, during which the system consumed the energy of three 100-Ah batteries. The use of DVRs extended the video and audio storage capabilities from 12 h to 12 days (using a 100 GB Archos 700), and lowered the power consumption of the system by a factor of four. One new 100-Ah battery was enough to power the system for 6 days. With two 100-Ah batteries, we could record continuous video and sound without intervention for 9 days using an 80 GB Archos 504, or for 12 days using a 100 GB Archos 700. After this time, it was necessary to replace the batteries and DVR units. Changing DVR units was more convenient than downloading the recordings because data transfer from the unit to the computer was too time consuming to be carried out in the field.

The cost of one complete system was about 520 euro, including a camera (100 euro), 50 m cable (50 euro), DVR unit (200 euro), microphone (20 euro) and battery (150 euro). For continuous monitoring, a complete system is required for each nest, plus one extra DVR unit and one extra battery. These needed to be changed every 6 days, and cost an additional 350 euro. We monitored up to three nests at the same time, and found that one extra DVR (a total of four) and two extra batteries (a total of five) were sufficient for this.

Discussion

The video monitoring system we have described is relatively inexpensive, and easy to assemble. The main components of the system are widely used in commercial surveillance systems. Cameras are available with various focal lengths and different numbers of LEDs (12 or 24), so the type of camera can be altered according to the size of, and distance to, the animal being monitored.

The DVRs we used are popular consumer electronic products with similar functionality to Apple iPods, apart from the ability to record video signals from external cameras. New models of Archos recorders are equipped with up to 320 GB hard drives, which could potentially record 36 days of video and sound. If powered by six 100-Ah batteries, such a system could be left for 36 days without intervention, which would greatly reduce maintenance efforts.

A major advantage of this system is that entire broods can be recorded over a long time period, without interruption. Without the ability to continuously monitor videos, visits of predators and incidents of predation might be easily missed due to their low frequency. The system also proved useful for studying the behaviour of nesting birds, particularly their interactions. We were able to quantify social interactions in Kagus (Theuerkauf et al. 2009a) and discovered polyandry in New Caledonian Parakeets (Theuerkauf et al. 2009b).

We believe that this system is not only applicable to nesting birds, but to any field situation where long-term continuous audio/video recording is required, such as at den sites, prey sites, drinking/feeding sites and animal highway passages. Because the system gathers large amounts of data with relatively little effort, it expands the potential for detailed behavioural studies of animals in the wild, especially the quantification of animal time budgets, interactions and species assemblages at gathering points.

Table 1

 1 Tally of various events recorded during video monitoring of endemic birds species in New Caledonia, from 2002 to 2009

	Event	Kagu (7,637 h,	New Caledonian Parakeet	Horned Parakeet	New Caledonian Whistler
		24 broods)	(9,606 h, 12 broods)	(4,761 h, 4 broods)	(293 h, 1 brood)
	Rat visits	72	16	8	0
	Predation	0	0	1 b	1 c
	Feeding of chicks	1,116	2,273	287	403
	Visits by other individuals of the	44	497 a	0	0
	same family (excluding parents)

a Visits of second male, genetically proved to be second father

(Theuerkauf et al. 2009b)

b Predation by introduced Black Rat c Predation by endemic New Caledonian Friarbird (Philemon diemenensis)

Acknowledgements This study was part of the research project "Impact of introduced mammals and habitat loss on endemic birds of New Caledonia", done in cooperation with the Direction de l'Environnement (Province Sud, New Caledonia), which issued all permits for this study, and financed by the Loro Parque Fundación (Spain), Polish Ministry of Science and Higher Education (Grant 2P04F 001 29), Conservation des Espèces et Populations Animales (France), La Fondation Nature et Découvertes (France), Fonds für bedrohte Papageien-Zoologische Gesellschaft für Arten-und Populationsschutz (Germany), and doctoral grants from Province Sud (to SR) and the University of Tasmania (to AL). We thank M. Broersen, C. Chatreau, P. de Pous, D. Dingemans, S. Duijns, B. Michielsen, E. Minnema, L. Nijdam, H. Theuerkauf, J. van Dijk, M. van Opijnen and J. Wardenaar for their help during field work.


Awais Sani

Philippe Coussy

Cyrille Chavet

An Approach Based on Edge Coloring of Tripartite Graph for Designing Parallel LDPC Interleaver Architecture

A practical and feasible solution for LDPC decoder is to design partially-parallel hardware architecture. These architectures are efficient in terms of area, cost, flexibility and performances. However, this type of architecture is complex to design since concurrent read and write accesses to data have to be performed at each time instance without any conflict. To solve this memory mapping problem, we present in this paper, an original approach based on a tripartite graph modeling and a modified edge coloring algorithm to design parallel LDPC interleaver architecture.

INTRODUCTION

Low-density parity-check (LDPC) codes [START_REF] Gallager | Low Density Parity Check Codes[END_REF] has gained a lot of attention in information theory community thanks to their near Shannon limit error correction capabilities and the explicit parallelism exhibited by their iterative decoding algorithm. These codes have already been included in several wireless communication standards such as DVB-S2 and DVB-T2 [START_REF]Frame structure channel coding and modulation for the second generation digital terrestrial television broadcasting system (DVB-T2)[END_REF], WiFi (IEEE 802.11n) [START_REF]Wireless LAN Medium Access Control and Physical Layer specifications: Enhancements for Higher Throughput[END_REF] or WiMAX (IEEE 802.16e) [START_REF]Air interface for fixed and mobile broadband wireless access systems[END_REF]. LDPC codes are linear block codes and are represented either by a sparse parity check matrix H or by a bipartite graph which is called Tanner graph [START_REF] Tanner | A recursive approach to low complexity codes[END_REF]. Figure 1.a shows the tanner graph of a LDPC code, which consists of two sets of vertices: variable node set (VN) and check node set (CN). A data v i ∈ VN represents one bit in the codeword (i.e. data to be processed) whereas c j ∈ CN represents a check equation used in generating parity check bits (i.e. operation to be done on the data). A v i is connected to a c j by an edge if and only if v i is checked by c j . The decoding process is carried out by an iterative messagepassing algorithm called "Belief Propagation Algorithm" [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible reference[END_REF]. In this algorithm, VN and CN iteratively exchange their softinformation to qualify the likelihood of the variable in accordance with the associated parity-check equation [START_REF] Gallager | Low Density Parity Check Codes[END_REF]. In literature, currently three main families of LDPC decoder architecture have been proposed:

• Fully-Parallel decoder architectures • Serial decoder architectures • Partially-Parallel decoder architectures Fully-Parallel decoders suffer from prohibitive area and serial decoders from low throughput. Thus the only LDPC decoder architecture fulfilling the need of current communication standards is partially-parallel architecture. In partially-parallel architecture several processing elements PEs are used and set of variable nodes and set of check nodes are allotted to each PE. High throughput requirement can be achieved using a proper number of PEs, while the interconnection network cost tends to be less critical as compared to fully-parallel implementation. Typical architecture for partially-parallel decoder is shown in Figure 1.b in which P PEs are always connected with B memory banks where P = B. While designing partially-parallel decoder architecture, the implementation issues mainly arise due to the communication structure between VNs and CNs whereas the computation at variable node and check node is quite simple. Moreover, partiallyparallel architecture suffers from memory accesses collision problem i.e., more than one PE concurrently accesses the same memory bank to read or write data. Hence, the communication structure becomes more and more challenging to design with the increase in the number of nodes, the number of iterations and the parallelism. In this paper, we present a memory mapping methodology based on tripartite graph which is able to provide all the PEs conflict free parallel access to the memory banks. This algorithm provides conflict free memory mapping for all types of decoding methods, codeword lengths, code types and code rates. The remainder of the paper is organized as follows. Section 2 presents a state of the art related to partially-parallel LDPC decoder design. Section 3 introduces the mapping problem. Section 4 defines concepts related to graph in order to understand the proposed approach. Section 5 details the mapping algorithm we propose. Finally, section 6 explains the algorithm through a pedagogical example.

RELATED WORKS

Currently three classes of approaches to design partially-parallel LDPC decoder architectures exist to tackle the collision problem:

• Design LDPC codes to avoid collision problem [START_REF] Mansour | High-throughput, LDPC decoders[END_REF], [START_REF] Chen | A FPGA and ASIC implementation of rate 1/2, 8088b irregular low density parity check decoder[END_REF],

• Use extra memory elements and control logic in the interconnection network in order to remove conflicts [START_REF] Theocharides | Implementing LDPC Decoding on a Network-on-Chip[END_REF], [START_REF] Kienle | Implementation Issues of Scalable LDPC-Decoders[END_REF], [START_REF] Moussa | Binary de Bruijn on-chip netwok for a flexible multiprocessor LDPC decoder[END_REF],

• Find a memory mapping to provide conflict free access to all the memory banks at any time instance [START_REF] Quaglio | Interconnection Framework for High-Throughput, Flexible LDPC Decoders[END_REF], [START_REF] Tarable | Mapping interleaving laws to parallel turbo and LDPC decoder architectures[END_REF], [START_REF] Chavet | Static Address Generation[END_REF]. In the first category of decoder implementation, structured or architecture oriented LDPC codes are designed in order to avoid conflicts in accessing data from memory banks. These codes remove the memory access conflicts and simplify the interconnection network through the use of a barrel shifter [START_REF] Mansour | High-throughput, LDPC decoders[END_REF] or a customized network [START_REF] Chen | A FPGA and ASIC implementation of rate 1/2, 8088b irregular low density parity check decoder[END_REF]. However, constraints in the development of structured LDPC codes may cause degradation in code performance. In the second class of decoder implementation, memory access conflicts are removed either through the addition of extra memory elements or complex interconnection network or both. In [START_REF] Theocharides | Implementing LDPC Decoding on a Network-on-Chip[END_REF], configuration memories are used along with 2D-mesh network for LDPC codes of different block size and code rates. In [START_REF] Kienle | Implementation Issues of Scalable LDPC-Decoders[END_REF], concurrent accesses to the same memory bank are avoided through the use of heterogeneous network. However, this network becomes complex with increasing degree of parallelization and suffers from reduction in the achievable throughput. In [START_REF] Moussa | Binary de Bruijn on-chip netwok for a flexible multiprocessor LDPC decoder[END_REF], binary de Bruijn network is employed for providing flexible on-chip network for LDPC decoder. Concurrent accesses to the same memory bank are avoided through dedicated routing algorithm which deflects one of the conflicted packets at the router. The flexibility in these complex interconnection networks is paid through additional hardware, increased decoding latency and power consumption. In the last class, methodologies for solving collision problem are proposed to map the data in different memory banks for conflict free concurrent read/write accesses. In [START_REF] Quaglio | Interconnection Framework for High-Throughput, Flexible LDPC Decoders[END_REF], the authors propose to use a mapping algorithm to remove memory conflicts in flexible LDPC decoders. However, the proposed approach is based on a simulatedannealing algorithm, so the user cannot predict when the algorithm will end. Moreover, it fails to optimize either the storage elements or the interconnection network. Finally, different heuristics [START_REF] Tarable | Mapping interleaving laws to parallel turbo and LDPC decoder architectures[END_REF], [START_REF] Chavet | Static Address Generation[END_REF] have been proposed to solve the mapping problem in turbo and LDPC decoding. However, they consider in-place memory accesses in which data have to be read from and write to the same memory location. Finally, conflict graph can be used. In this model, a node represents a data and two nodes are connected if and only if the associated data are accessed at the same time. Node coloring approach can then be used to solve the mapping problem: each color corresponds to one memory bank. Unfortunately only one color can be assigned to one node, i.e. a data can be stored in only one memory bank. This constraint may require more memory banks than needed (see [17] for more details). Similarly, number of algorithms have been proposed for coloring the edges of a bipartite graph by constructing partitions ( [START_REF] Gabow | Using Euler partitions to edge color bipartite multigraphs[END_REF] and [START_REF] Cole | On edge coloring bipartite graphs[END_REF] for example). Unfortunately, like node coloring approaches they can not be used to solve the mapping problem because each data is supposed to be

PROBLEM FORMULATION

To explain the problem, we consider a set of K data {l 1 , l2,…, l K } and a set of P processing elements {PE 1 , PE 2 ,…, PE P } which iteratively process these K data in N time instances {t 1 , t 2 ,…, t N }. In order to store these K data and to achieve parallel iterative processing for high throughput, a set of B memory banks {b 0 , b 1 ,…, b B-1 }, where B = P, is used. All the memory banks have the same size M which is equal to M = K/P.

Mapping problem

Store K data in B memory banks in such a manner that P processing elements can, at each time instance, access B memory banks in parallel for first reading P data and then writing back these P data without any conflict.

To explain the problem, we introduce a mapping matrix in which we have P rows, related to the processing elements, and N columns, related to the time instances t i . Each column is further divided into three sub-columns. First sub-column shows the data which need to be accessed in parallel by P processing elements at t i whereas second sub-column contains the memory banks from where data are read and third sub-column represents the memory banks in which these data are written at t i . Also, data in each row are processed by the processing element connected with this row. Figure 2 represents the mapping matrix in which we have K = 6, P = B = 3, M = 2 and N = 6. Each data is processed 3 times which shows the iterative nature of the data access. However, data accesses are interleaved in time and there is no regularity in processing the data; e.g., data 3 is successively processed in time instances t 1 and t 2 whereas the first access to the data 4 occurs at time instance t 3 .

R W R W R W R W R W R W PE 1 1 3 6 5 4

Parallelism Time

Figure 2: Mapping Matrix Memory Mapping Constraints

To successfully map the data (i.e. to allow conflict free parallel memory access) (1) in a given number of memory banks and (2) to tackle the iterative nature of data access in error correction coding, the mapping matrix must fulfill the two following constraints:

1-At each time instance, all the memory banks have to be used one and only one time. 2-The bank of the last write access to a data must be the same as the bank of its first read access.

To tackle the mapping problem, we introduce the concept of multiple read and multiple write access. Therefore, we can access data in two ways: we can either (1) read and write a data from the same memory bank (if it is possible) i.e. like in classical approaches (see [START_REF] Tarable | Mapping interleaving laws to parallel turbo and LDPC decoder architectures[END_REF], [START_REF] Chavet | Static Address Generation[END_REF] for example) or (2) read a data from one memory bank and then write it in a different one as we propose in this paper. The proposed approach, which allows to access data with an in-place strategy, is based on edge coloring of tripartite graph and is presented in section 5.

DEFINITIONS

A graph G = (V, E) is a collection of nodes, set V, and edges, set We finally define a regular partition in semi regular tripartite graph as a partition that respects either Lemma 1 or Lemma 2.

E. If v,w ∈ V then an edge e(v,
An edge coloring of G is an assignment of a color to each edge in G. An edge chromatic number, χ`(G), is the fewest number of colors necessary to color each edge of a graph so that no two edges incident to the same vertex have the same color.

PROPOSED APPROACH

The proposed approach is divided into two parts. In the first part, we model our problem as a tripartite graph based on mapping matrix i.e., the interleaving law. In the second part, we apply a 2-step coloring approach on the tripartite graph to color its edges so that data can be read from and be written to the memory without any conflict at any time instance.

Modeling

A Tripartite graph G = (T R ∪ T W ∪ L, E
) is constructed based on mapping matrix (e.g. Figure 3). Vertex sets T R and T W represent all the time instances at which data are read and written respectively. Vertex set L represents all the data used in the computation. An edge (l, t aR ) is incident to the data vertex l and to the read access time instance vertex t aR if l needs to be read at t aR . Similarly, an edge (t cW , l) is incident to l and to the write access time instance vertex t cW if l needs to be written at t cW . Moreover, at each data vertex l, edges (l, t aR ) and (t cW , l) are placed on two different sides of l as shown in Figure 3.b.

In order to follow the mapping constraint and for functional correctness of data accesses, the memory bank from which data is read from its current access must be the same as the memory bank in which the data is written in its previous access. If i is the access order of data l and n is the total number of times the data l is accessed, then i = {1, 2,……, n}.

Definition: two edges (l, t aR ) and (t cW , l) are called related edges if i = j -1 for i > 1 n for i = 1 where i = Order(l, t aR ), j = Order(t cW , l) and where Order(l, t aR ) and Order(t cw , l) are respectively the read and the write access order of data l.

If colors of edges represent memory banks (as shown in section 5.2), then at each data vertex l, related edges must have the same color. Related edges representation of data node l for i = 3 is shown in Figure 3.c. Related edges are connected with dotted line.

One interesting property of parallel LDPC decoding architecture is that the number of accesses to data or processing elements at any time instance is always equal which implies that corresponding tripartite graph is always semi regular at vertex set T R and T W . This implies that all the time nodes (either for read or write accesses) in the tripartite graph have the same degree d t =P.

Since vertex set T R and T W are always semi regular, the regular partitions contain all the vertices of both T R and T W with the degree requirement mentioned in Lemma 1 and 2.

2-step coloring approach

A 2-step algorithm is used to color the edges of tripartite graph and hence to find a conflict free memory mapping: (1) tripartite graph is divided into regular partitions and then (2) each regular partition is colored independently.

Step I, Partitioning Algorithm:

The algorithm (see Figure 4.a) begins constructing a path p curr by selecting a data vertex l curr. Process of addition is then invoked to add an edge (l curr , t aR ) into p curr and its related edge (t cW , l curr ) into the current set of related edges Relp curr . Process of deletion is then applied to remove from G tmp all invalid and their related edges from time nodes that belong to p curr .

Definition: An edge is invalid if its selection decreases the number of edges at any read or write access vertex to less than d t '. Otherwise, it is a valid edge.

Process of addition is again invoked at t curr,R to add another valid edge (t aR , l next ) into p curr and to reach at l next . The related edge of (t aR , l next ) is included in Relp curr . Process of deletion is then applied. At that point p curr = {(l curr , t aR ), (t aR , l next )}. The algorithm continues by alternating applying process of addition and process of deletion until p curr is completed, i.e. the process of addition does not find any valid edge to be included in p curr . At that point, p curr and Relp curr are included in the current partition Par curr. While the partition is not regular (i.e. degree of valid edges at each read and write access time nodes is exactly d t '), the algorithm starts constructing another path by using the remaining edges of G tmp . The algorithm starts constructing another partition on the remaining graph G tmp = G -Par cur until G tmp is not empty. Step II, Coloring Algorithm: Our coloring algorithm (which flow chart is shown in Figure 4.b), colors each partition with at most two colors thanks to the construction of regular partitions.

Apply process of addition and deletion alternately on

For each partition Par curr , the algorithm starts by choosing any read access time vertex t init,R whose edges are still not colored. First color is given to edge (t init,R , l) and its related edge (l, t curr,W ). Since at most two edges exist at each time vertex thanks to the construction of regular partitions, the algorithm gives a second color to (t curr,W , l next ) and its related edge (l next , t curr,R ). After reaching at t curr,R , the algorithm tests whether t curr,R = t init,R . If not, then algorithm gives first color to the 2 nd edge at t curr,R and its related edge until algorithm reaches at t init,R . In case algorithm reaches t init,R , it tests whether partition is completely colored.

If not, then algorithm chooses another node as t init,R and repeats the same process until Par curr is completely colored.

Partitioning and coloring algorithms are explained through a pedagogical example in the next section.

PRACTICAL IMPLEMENTATION

Let us present an example based on the mapping matrix in Figure 2. The first step is the construction of tripartite graph which is already depicted in Figure 3.a. This semi regular tripartite graph has each time vertex with degree d t = 3. Following Lemma 2, we will have after applying the partitioning algorithm two partitions: one partition in which each time vertex's degree d t ' is 2 and one partition in which d t ' is 1.

The algorithm starts by selecting data 1 and then invokes the process of addition which adds the first available edge (1, t 1R ) into the path p 1 , leading to p 1 = {(1, t 1R )}. The related edge of (1, t 1R ) that is (1, t 6w ) is also included in the current set Relp 1 . The selected read access edges and their related edges are represented by bold lines in Figure 5.a. The process of deletion is invoked but no invalid edge is found to be deleted. After the construction of Par 2 , the partitioning algorithm finds that the graph is completely traversed and is terminated.

CONCLUSION

In this paper, we proposed an approach to solve the mapping problem that arises when designing parallel LDPC interleaver. The concept of tripartite edge coloring has been introduced to design hardware architectures supporting multiple read/write accesses. This approach can be used to solve the mapping problems in other signal processing, communication domains... In future works, additional constraints will be added to take into account the complexity of interconnection network.

REFERENCE Easing: a Design Methodology for Parallel Interleaver Architecture". In proceeding ICASSP 2010.

[17] C. Chavet, P. Coussy, "A memory Mapping Approach for Parallel Interleaver design with multiples read and write accesses". In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS) 2010.

  graph of an LDPC b. Decoder architecture Figure1: LDPC code and decoder architecture stored in one memory bank only i.e. only one color can be assigned to one edge.

Figure 3 :

 3 Figure 3: Tripartite Graph Representation

Figure 4 :

 4 Figure 4: Partitioning and Coloring Algorithms

Figure 7

 7 .b. The algorithm continues until the partition is completely colored. The complete coloring of Par 1 is shown in Figure 8.a. The coloring of Par 2 is easier: all the edges are colored with one single color b 2 represented by grey big dotted lines in Figure 8.b because d t ' = 1 as already mentioned. The complete coloring of G is shown in Figure 9.a. The corresponding mapping matrix is presented in Figure 9.b.

b 1 3 b 2 b 1 6 b 0 b 1 5 b 2 b 0 4 b 2 b 1 2 b 2 b 1 2 b1 b0 5 b0 b2 1 b1 b0 6 b1 b1 3 b1 b2 1 b0 b0 3 b 2 b 2 6 b 1 b 0 4 b 2 b 2 2 b 0 b 2 5 b 0 b 0 4 b 1 b 2

 12

Figure 9 :

 9 Figure 9: Conflict free edge coloring of G and corresponding mapping matrix

Figure 6 :

 6 Figure 6: Path construction through Partitioning Algorithm

  The degree of vertex v is the number of edges incident to v. A graph is regular if all vertices have the same degree. A graph is semi regular, if all the vertices in any of its vertex set have the same degree.A path P is a sequence of edges (v 1 , v 2 ), (v 2 , v 3 ),..., (v n-1 , v n ). The ends of P are vertices v 1 and v n . If v 1 ≠ v n , P is open; otherwise P is closed. A graph is connected ifthere is a path between any two distinct vertices. If S i is the vertex set whose all the vertices have the same degree in a semi regular tripartite graph G = (S 1 ∪ S 2 ∪ S 3 , E) then partition in G is defined as a subgraph containing all the elements of S i. (i.e. S 1 , S 2 or S 3 ) Lemma 1: When the degree d t of a vertex of S i in a semi regular graph is even then we have d t /2 partitions in which each vertex's degree d t ' is 2. Lemma 2: When the degree d t of a vertex of S i in a semi regular graph is odd then we have  

	d	t	2	partitions in which each vertex's degree d t ' is
	2 and one subgraph in which d t ' is 1.

w) ∈ E is incident to v and to w, and vertices v and w are said adjacent. A subgraph of G is a graph whose vertices and edges are in G. To delete edge (v,w) from G means to form the subgraph G -(v,w), consisting of all vertices of G and all edges of G except (v,w).

A graph G = (S 1 ∪ S 2 ∪ S 3 , E) is tripartite, if a set of graph vertices decomposed into three disjoint sets such that no two graph vertices within the same set are adjacent i.e. S 1 ∩ S 2 ∩ S 3 =∅.

st Read Access 2 nd Read Access Last Read Access 1 st Write Access 2 nd Write Access Last Write Access 1 st Write Access 2 nd Write Access 3 rd Write Access 1 st Read Access 2 nd Read Access 3 rd Read Access

		t 1R	1	t 1W
		t 2R	2	t 2W
	Time	t 3R t 4R	3 4	t 3W t 4W
		t 5R	5	t 5W
		t 6R	6	t 6W
		Read Access Data Elements	Write Access
		a. Tripartite Graph of Figure. 2.
		1 b. Data Node l Representation	c. Related edges representation for i = 3 of l

  At this point, the number of access at t 1R and t 6W increases to 2 and the other unselected edges at t 1R and t 6W becomes invalid edges. So the process of deletion removes the invalid edge (4, t 6W ) and its related edge (4, t 3R ) as shown in Figure5.b. 5W )} as shown in Figure6.a. The algorithm adds p 1 and Relp 1 into Par 1 but Par 1 does not form a regular partition because t 2R and t 5R are not included in p 1 . So the algorithm starts to construct a new path p 2 by again invoking the process of addition and deletion. The resultant path p 2 = {(3, t 5R ), (t 5R , 5), (5, t 2R ), (t 2R , 6)} is shown in Figure6.b. Now the partition Par 1 is the union of all the paths and their related edge sets, Par 1 = p 1 + p 2 + Relp 1 + Relp 2 . Again the algorithm tests whether Par 1 constitutes a regular partition. This time the test is successful and the Par 1 is declared as regular partition (see Figure6.c). After the construction of Par 1 , the algorithm finds that the graph is not completely traversed. So the algorithm deletes Par 1 to obtain the graph G tmp = G -Par 1 and applies again the processes on G tmp to obtain the Similarly partition Par 2 is the sum of all the traversed paths and their related edges as given below, Par 2 = p' 1 + p' 2 + p' 3 + p' 4 + p' 5 + p' 6 + Relp' 1 + Relp' 2 + Relp' 3 + Relp' 4 + Relp' 5 + Relp' 6 (see Figure6.d).

	The algorithm continues by alternately invoking the two processes until
	the path p 1 reaches at t 6R . We have at that point p 1 = {(1, t 1R ), (t 1R , 2), (2,
	t 4R ), (t 4R , 6), (6, t 3R ), (t 3R , 1), (1, t 6R )} and Relp 1 = {(1, t 6w ), (2, t 6W ), (2,
	t 1W ), (6, t 3W ), (6, t 2W ), (1, t 1w ), (1, t 3w )}. The edges of p 1 and Relp 1 are
	shown in Figure 5.c. At this point, the process of addition can choose
	either (t 6R , 2) or (t 6R , 4) to augment p 1 . But choosing (t 6R , 2) makes (t 6R ,
	4) and its related edge (4, t 5W ) invalid because the number of edges at
	t 5W becomes less than 2. So the process adds (t 6R , 4) (the only available
	valid edge) into p 1 , (4, t 5W ) into Relp 1 and declares (t 6R , 2) and its related
	edge (2, t 4W ) as invalid as shown in Figure 5.d.
	At this stage, the algorithm finds that no more valid edges available at
	data vertex 4 to be added in p 1 = {(1, t 1R ), (t 1R , 2), (2, t 4R ), (t 4R , 6),(6,
	t 3R ), (t 3R , 1), (1, t 6R ), (t 6R , 4)} and Relp 1 = {(1, t 6w ), (2, t 6W ), (2, t 1W ), (6,
	t 3W ), (6, t 2W ), (1, t 1w ), (1, t 3w ), (4, t paths, p' 1 = {(2, t 6R )}, p' 2 = {(3, t 1R )}, p' 3 = {(3, t 2R )}, p' 4 = {(4, t 3R )},
	p' 5 = {(4, t 5R )}, p' 6 = {(5, t 4R )}.

The process of addition continues by adding the edge (t 1R , 2) into the path p 1 and its related edge (2, t 6W ) into Relp 1 . We have now p 1 = {(1, t 1R ), (t 1R , 2)} and Relp 1 = {(1, t 6w ), (2, t 6W )}.

  Path construction through Partitioning AlgorithmAfter the generation of the partitions, each partition is colored depending on the degree d t ' of its time node. For example, the Par 1 is colored with, d t ' = 2, colors and the Par 2 is colored with, d t ' = 1, color. To color the partition Par 1 , the algorithm starts from any read access time vertex whose edges are still not colored. In this example, the algorithm begins from t 1R and gives one color b 0 to (t 1R , 1) and its related edge (1, t 6W ) to reach at t 6W . At t 6W , the algorithm then gives different color b 1 to the other edge (t 6W , 2) and its related edge (t 1R , 2) to reach at t 1R as shown in Figure7.a. In this figure, grey straight line represents color b 0 and grey dotted line represents color b 1 . The algorithm finds that t 1R is completely colored so it chooses another uncolored read access time vertex t 2R and gives color b 0 to (t 2R , 5) and its related edge (5, t 5W ) to reach at t 5W . At t 5W , the algorithm gives different color b 1 to the other edge (t 5W , 4) and its related edge (t 6R , 4) to reach at t 6R as shown in

	t 1R	1	t 1W	t 1R	1	t 1W
	t 2R	2	t 2W	t 2R	2	t 2W
	t 3R	3	t 3W	t 3R	3	t 3W
	t 4R	4	t 4W	t 4R	4	t 4W
	t 5R	5	t 5W	t 5R	5	t 5W
	t 6R	6	t 6W	t 6R	6	t 6W
	Read Access Data Elements	Write Access	Read Access Data Elements	Write Access
		a.			b.
	t 1R	1	t 1W	t 1R	1	t 1W
	t 2R	2	t 2W	t 2R	2	t 2W
	t 3R	3	t 3W	t 3R	3	t 3W
	t 4R	4	t 4W	t 4R	4	t 4W
	t 5R	5	t 5W	t 5R	5	t 5W
	t 6R	6	t 6W	t 6R	6	t 6W
	Read Access Data Elements	Write Access	Read Access Data Elements	Write Access
		c.			d.
		Figure 5:

  Conflict Free Edge Coloring of Par 1 and Par 2

						t 1R	1	t 1W	t 1R	1	t 1W
						t 2R	2	t 2W	t 2R	2	t 2W
						t 3R	3	t 3W	t 3R	3	t 3W
						t 4R	4	t 4W	t 4R	4	t 4W
						t 5R	5	t 5W	t 5R	5	t 5W
						t 6R	6	t 6W	t 6R	6	t 6W
						Read Access Data Elements	Write Access	Read Access Data Elements	Write Access
							a.	b.
						t 1R	Figure 8: 1	t 1W
						t 2R	2	t 2W
						t 3R	3	t 3W
						t 4R	4	t 4W
						t 5R	5	t 5W
						t 6R	6
						Read Access Data Elements	Write Access
	t 1R	1	t 1W	t 1R	1	t 1W
	t 2R	2	t 2W	t 2R	2	t 2W
	t 3R	3	t 3W	t 3R	3	t 3W
	t 4R	4	t 4W	t 4R	4	t 4W
	t 5R	5	t 5W	t 5R	5	t 5W
	t 6R	6	t 6W	t 6R	6	t 6W
	Read Access Data Elements Write Access	Read Access Data Elements Write Access
		a.			b.

Figure 7: Conflict Free Edge Coloring of Par 1


Kostas Danas
email: kdanas@lms.polytechnique.fr

Sunny Kankanala
email: sundeep_kankanala@bd.com

Nicolas Triantafyllidis

Magnetorheological Elastomers

Magnetorheological Elastomers: Experiments and Modeling

Keywords: magneto-mechanics, multi-physics, elastomers

come   L'archive ouverte pluridisciplinaire

Introduction

Devices made of magneto-rheological elastomers (MREs) have been proposed for a number of engineering applications due to the potentially controllable nature of their mechanical properties [START_REF] Ginder | Magnetorheological elastomers : Magnetorheological elastomers : properties and applications, Smart Structures and Materials[END_REF]. Although there has been a substantial effort in theoretical descriptions of these types of solids (e.g. [START_REF] Borcea | On the magneto-elastic properties of elastomer-ferromagnet composites[END_REF], [START_REF] Dorfmann | Magnetoelastic modelling of elastomers[END_REF] and [START_REF] Kankanala | On finitely strained magnetorheological elastomers[END_REF]), there have not been many studies-to the best knowledge of the authors-dealing with the constitutive modeling and characterization of MREs. Material models for other magnetoelastic solids, however, have been presented in the literature. For example, [START_REF] Moffett | Characterization of Terfenol-D for magnetostrictive transducers[END_REF] gave the first characterization of Terfenol-D. In this regard, due to the absence of adequate constitutive description for MREs, it has been difficult to quantify the extent of benefits that a MRE device could offer. The objective of this work is twofold ; first, we present experiments of iron-particle-filled elastomers subjected to prestressing and arbitrary magnetic fields and second, we carry out a phenomenological modeling of these materials.

Experiments and modeling

Experiments are carried out for MREs comprising 25% of iron particles of sizes ranging from 0.5µm to 5µm cured in a 0.5T magnetic field. The application of a magnetic field during the curing process leads to formation of particle chains aligned with the curing field direction. The experiments involve three different setups ; (a) uniaxial stress tests in the direction of a magnetic field which is aligned with the particle chains, (b) uniaxial stress tests in the direction of a magnetic field which is perpendicular to the particle chains and (c) simple shear tests where the particle chains are initially aligned with the applied magnetic field, as shown in Fig. 1.

The second part of this work pertains in finding an energy density function ψ that best fits the experiments reported above. As already pointed out, the material under investigation is a transversely isotropic composite since the iron particles form chains along a certain direction. This implies that the free energy density ψ should also depend on the unit vector N (see Fig. 1), which defines the initial orientation of the particle chains. Thus,

ψ = ψ(C, N, M), C = F T • F, N • N = 1, ( 1
)
where F is the material's deformation gradient (F T denotes its transpose), C denotes the right "Cauchy-Green" tensor and M the specific magnetization. Following [START_REF] Kankanala | On finitely strained magnetorheological elastomers[END_REF] (c.f. relations (2.42) and (2.44) in that reference), we obtain the following expressions for the total Cauchy stress σ and the magnetic field h

σ = ρ 2F • ∂ ψ ∂C • F T + µ 0 (Mh + hM) + µ 0 hh - 1 2 (h • h)I , µ 0 h = ∂ ψ ∂M , ( 2
)
where ρ is the current material density. Note that in vacuum (ρ = 0), the total stress is non-zero and equals the Maxwell stress

µ 0 [hh -(1/2)(h • h)I].
Theoretical predictions, based on the energy density of equation ( 1 ) of a MRE comprising 25% of iron particles of sizes ranging from 0.5µm to 5µm cured in a 0.5T magnetic field. The application of a magnetic field during the curing process leads to formation of particle chains aligned with the curing field direction. In the bottom figure are experimental (discrete marks) and theoretical (solid lines) results showing the influence of the magnetic field on the MRE's simple shear response with G denoting the shear modulus.

FIGURE 1 -

 1 FIGURE 1 -Top left, shows the schematics of a specimen subjected to simple shear in the presence of a magnetic field. Top right shows an electron micrograph (from[START_REF] Ginder | Magnetorheological elastomers : Magnetorheological elastomers : properties and applications, Smart Structures and Materials[END_REF]) of a MRE comprising 25% of iron particles of sizes ranging from 0.5µm to 5µm cured in a 0.5T magnetic field. The application of a magnetic field during the curing process leads to formation of particle chains aligned with the curing field direction. In the bottom figure are experimental (discrete marks) and theoretical (solid lines) results showing the influence of the magnetic field on the MRE's simple shear response with G denoting the shear modulus.


K Danas
email: kdanas@lms.polytechnique.fr

P Ponte Castañeda

Presqu'île de Giens (Var) Failure of elasto-plastic porous materials subjected to triaxial loading conditions

Keywords: ductile fracture, Lode parameter, plasticity

 to study the influence of the Lode parameter and the stress triaxiality on the failure of metallic materials. This model is based on the "second-order" or "generalized secant" homogenization method [2] and is capable of handling general "ellipsoidal" microstructures (i.e., particulate microstructures with more general orthotropic overall anisotropy) and general three-dimensional loading conditions.

Introduction

Failure and ductile fracture of metallic materials has received a lot of attention the last sixty years. One of the main reasons for material failure is the presence or/and nucleation of voids and micro-cracks which tend to evolve in volume fraction, shape orientation as a result of the applied loading conditions. For several years, it was believed that the stress triaxiality, denoted here as X Σ and defined as the ratio between the mean stress to the von Mises equivalent or effective deviatoric stress, is the main loading parameter that controls ductile fracture. In particular, large amount of experimental data [START_REF] Hancock | On the mechanisms of ductile fracture in high-strength steels subject to multi-axial stress-states[END_REF][START_REF] Johnson | Fracture characteristics of three metals subjected to various strains, strain rates, temperatures and pressures[END_REF] has shown a monotonic decrease of material ductility with the increase of the stress triaxiality. Nonetheless, recent experimental evidence [START_REF] Barsoum | Rupture mechanisms in combined tension and shearÑExperiments[END_REF][START_REF] Dunand | Hybrid experimental-numerical analysis of basic ductile fracture experiments for sheet metals[END_REF] indicate a substantial decrease of the material ductility with decrease of stress triaxiality and certain shear loading conditions. In these studies, it has been identified that a second loading parameter, the Lode parameter, L (or equivalently Lode angle, θ) controls the ductile fracture mechanism at low stress triaxialities. The Lode parameter is a function of the third invariant of the stress deviator and is used to distinguish between the different shear stress states that can be present in a loading history (see details in the following section). In the present work, we make use of the "secondorder" model [START_REF] Danas | A finite-strain model for anisotropic viscoplastic porous media : I -Theory[END_REF] (SOM) to study the influence of the Lode parameter and the stress triaxiality on ductile failure.

Modeling and results

We consider a porous material with initially spherical voids subjected to purely triaxial loading conditions with the principal stresses σ 1 = σ 11 , σ 2 = σ 22 and σ 3 = σ 33 (σ i j = 0 for i = j) being aligned with the laboratory frame axes, e (1) , e (2) and e (3) , respectively. This allows for the definition of alternative stress measures appropriate for dilatational plasticity, which is the case in the context of porous materials. The three alternative measures are the von Mises equivalent stress (or effective stress), σ e , the mean stress, σ m , and the third invariant of the stress deviator J 3 defined all by

σ e = 3 J 2 = 3 s i j s i j /2, σ m = σ kk /3, J 3 = det(s i j ) = 1 3 s i j s ik s jk , (1)
where s i j = σ i j -σ m δ i j is the stress deviator. Using these definitions, we evaluate the Lode parameter, L, or equivalently the Lode angle, θ, and the stress triaxiality, X Σ , by the following expressions

L = -cos 3θ = 27 2 J 3 σ 3 e , X Σ = σ m σ e , (2) a)
b) where the hardening rate H = 0. The loss of ellipticity locus is identified with the critical equivalent plastic strain ε p e where the constitutive equations lose strong ellipticity leading to localized bifurcated solutions and long-wavelength instabilities. The hardening exponent is N = 0.1 and the initial porosity f 0 = 1%.

0 1 2 3 4 5 6 0 0.2 0.4 0.6 0.8 1 1.2 ε e p X Σ L = -0.97 θ =5 o L = 1, θ =60 o L = 0.5, θ =40 o L = 0, θ =30 o L = -0.5, θ =20 o L = -0.71, θ =15 o L = -0.87 θ =10 o L = -1 θ =0 o
L = -1 θ =0 o L = -0.97 θ =5 o L = -0.87 θ =10 o L = 1, θ =60 o L = 0.5, θ =40 o L = 0, θ =30 o L = -0.5 θ =20 o L = -0.71 θ =15 o
with -1 ≤ L ≤ 1 (or 0 ≤ θ ≤ π/3) and -∞ < X Σ < +∞. The values θ = κπ/3 (L = -1 and L = +1) and θ = (2κ + 1)π/6, with κ integer, correspond to axisymmetric shear and simple shear with superimposed hydrostatic pressure when X Σ is nonzero. When |X Σ | → ∞ and X Σ = 0 the loading is purely hydrostatic and purely deviatoric, respectively.

Fig. 1 shows SOM maps of the critical equivalent plastic strain ε p e attained when (a) the limit load (i.e., maximum in the σ e -ε e curve or equivalently critical hardening rate H = 0) and (b) the conditions for localization [START_REF] Rice | The localization of plastic deformation[END_REF] and loss of ellipticity (LOE) are reached as a function of the stress triaxiality X Σ and the Lode parameter L (or Lode angle θ). We find that the overall strain at localization depends strongly on the Lode parameter as well as on the stress triaxiality. According to the SOM model, these effects are due to the collapse of voids at low stress triaxialities where the initially spherical pores tend to become micro-cracks. This void collapse mechanism leads to the formation of shear or dilation localization bands depending on the value of the Lode parameter. On the other hand, at large stress triaxialities the main mechanism of failure is the increase of porosity, which leads to the overall softening of the porous material. The interplay of these two different mechanisms of localization (i.e., void shape change and porosity growth), leads to sharp, high-ductility corners on the localization locus map.

FIGURE 1 -

 1  Limit load and (b) loss of ellipticity maps as predicted by the SOM model as a function of the stress triaxiality X Σ and the Lode parameter L (or θ). The limit load locus is identified with the critical equivalent plastic strain ε p e where the hardening rate H = 0. The loss of ellipticity locus is identified with the critical equivalent plastic strain ε p e where the constitutive equations lose strong ellipticity leading to localized bifurcated solutions and long-wavelength instabilities. The hardening exponent is N = 0.1 and the initial porosity f 0 = 1%.