Selma Saidi

Yliès Falcone

Dynamic Detection and Mitigation of DMA Races in MPSoCs

Explicitly managed memories have emerged as a good alternative for multicore processors design in order to reduce energy and performance costs. Memory transfers then rely on Direct Memory Access (DMA) engines which provide a hardware support for accelerating data. However, programming explicit data transfers is very challenging for developers who must manually orchestrate data movements through the memory hierarchy. This is in practice very error-prone and can easily lead to memory inconsistency. In this paper, we propose a runtime approach for monitoring DMA races. The monitor acts as a safeguard for programmers and is able to enforce at runtime a correct behavior w.r.t the semantics of the program execution. We validate the approach using traces extracted from industrial benchmarks and executed on the multiprocessor system-onchip platform STHORM. Our experiments demonstrate that the monitoring algorithm has a low overhead (less than 1.5 KB) of on-chip memory consumption and an overhead of less than 2% of additional execution time.

I. INTRODUCTION

In recent Multiprocessor Systems-on-Chip (MPSoCs) design, a combination of Scratchpad Memories (SPM) [START_REF] Banakar | Scratchpad memory: design alternative for cache on-chip memory in embedded systems[END_REF] and Direct Memory Access (DMA) engines have been proposed as an alternative to traditional caches, where data (and sometimes code) transfers through the memory hierarchy are explicitly managed by the software. This is promising in terms of performance, energy, and silicon area. However the price to pay is clearly programming complexity, since the programmer/software has a disjoint view of the different levels of memories and must manually orchestrate data movements using explicit DMA operations. In this context, DMA races emerge as one of the regular issues programmers have to face.

In concurrent programming, Data racing refers to the situation where several threads perform conflicting accesses (i.e., at least one of them is a write) on a shared (global) variable with no proper synchronization between these accesses [START_REF] Savage | Eraser: a dynamic data race detector for multithreaded programs[END_REF]. In MPSoCs, the notion of DMA races is an extension of the classical notion of data races, where two or more DMA requests access the same memory region simultaneously and at least one request is a write operation. While data races result from a natural need of parallel programs to access shared data, DMA races usually result from a misuse of DMA operations in a program (e.g., a misplaced DMA-synchronization instruction or a misuse of DMA commands identifying tags). These errors are very common since the programmer is solely responsible of the correct management of DMA operations, which quickly becomes tricky when asynchronous DMA calls are involved.

Detecting data races in multithreaded, lock-based programs, is an extensive area of research, and a lot of techniques have been proposed to detect and prove the absence of races in a program. Some of these tools, such as [START_REF] Havelund | Model checking Java programs using Java PathFinder[END_REF], [START_REF] Aspinall | Formalising Java's data race free guarantee[END_REF], [START_REF] Dabrowski | A certified data race analysis for a Java-like language[END_REF], [START_REF] Rinard | Analysis of multithreaded programs[END_REF] or more recently [START_REF] Cuoq | Frama-C: a software analysis perspective[END_REF], rely on formal methods like static analysis, theorem proving and model checking. These techniques suffer from the state-space explosion problem which makes them hardly applicable for complex real size (industrial) applications. In contrast, even though they are not exhaustive, dynamic approaches are lightweight methods that have more precise information available at runtime and can thereby be used to react to errors. Approaches for dynamic data race detection such as Eraser [START_REF] Savage | Eraser: a dynamic data race detector for multithreaded programs[END_REF], Goldilocks [START_REF] Elmas | Goldilocks: a race and transactionaware Java runtime[END_REF] and [START_REF] Huang | Maximal sound predictive race detection with control flow abstraction[END_REF] are proposed to keep track of active locks when accessed.

In this paper, we also propose a dynamic approach, for the detection and correction of DMA races. In the embedded multi-core domain, only few work address the problem of DMA races (cf. [START_REF] Donaldson | Automatic analysis of dma races using model checking and k-induction[END_REF] and [START_REF] Donaldson | Scratch: a tool for automatic analysis of dma races[END_REF]). These approaches statically verify DMA operations, by automatically instrumenting the program using assertions. The instrumented program can then be analyzed using software model-checkers. One of the main drawbacks of these methods is their restriction to the verification of sequential programs (as opposed to concurrent ones). The work in [START_REF] Kistler | Detecting race conditions in asynchronous dma operations with full system simulation[END_REF] proposes a dynamic approach for DMA race detection as part of a full system simulation, however the overhead of their approach is not described and nothing is performed at runtime for data race correction.

We propose a monitoring algorithm which observes in an online fashion the arrival of a sequence of DMA events and emits a verdict each time a DMA race is detected. Moreover, it can enforce a correct and a DMA race-free execution of the program. The algorithm acts as a filter that does not allow the execution of a new DMA command that would create a race. The execution of this command is deferred to another point in time when no race is possible. The algorithm therefore changes the order of execution of DMA commands in a program and leads to a rescheduling of DMA requests. The enforced order of execution maintains the causality between dependent DMA requests in order to preserve the memory consistency of the program. The monitor is implemented in a simulation tool. We use traces extracted from industrial benchmarks and executed on the MPSoC platform STHORM [START_REF] Melpignano | Platform 2012, a many-core computing accelerator for embedded socs: performance evaluation of visual analytics applications[END_REF]. Our experiments demonstrate that the proposed approach induces a cheap overhead, both in terms of required on-chip memory and execution time delay due to the rescheduling of events.

II. RUNTIME MONITORING OF DMA RACES

A. Formalizing the Problem of DMA Races

In case of SPMs, the on-chip and off-chip memories are referred to as one global address space. A contiguous memory region in the global address space is defined by a pair (α, s)

where α is the address of the beginning of the region and s is the size of the region. The memory addresses denoted by this region are included in the interval [α, α + s].

When a processor needs data, it issues a transfer command to the DMA. Typically, a DMA command consists of a source address, a destination address, a block size1 and a tag to identify the command, the DMA then takes charge of the transfer. When the data transfer terminates, the processor is notified of its completion.

Definition 1 (DMA command): A DMA command for transferring a contiguous block of data is defined as a 4tuple (tag, srcα, dstα, s) where, tag is the identifier of the command, srcα is the source address, dstα is the destination address and s is the size of the block to transfer. Note that a DMA command involves two memory regions: (srcα, s) in read mode, and (dstα, s) in write mode.

Definition 2 (DMA event): At runtime, a (contiguous) DMA command is associated with a pair (e s , e d ) of DMA events: a start event e s that marks the beginning of the execution of the command at some time t, and an end event e d that marks the end of the execution of the command at some time t , with t > t. Both e s and e d are identified with the same tag of the corresponding DMA command.

Remark 1: Note that the execution time t -t of the command depends mainly on the size of the block to transfer along with some architectural hardware parameters (bandwidth, contentions, etc), and can be approximated statically using the DMA performance model defined in [START_REF] Saidi | Optimizing explicit data transfers for data parallel applications on the CELL architecture[END_REF], [START_REF] Saidi | Optimal 2d data partitioning for DMA transfers on MPSoCs[END_REF].

Definition 3 (DMA Trace):

A DMA trace is an ordered sequence of DMA events with the following constraints: a) For each DMA command i, the start event precedes the end event, that is: e s (i) ≤ p e d (i), where ≤ p denotes the precedence relation between events. b) A trace can contain two DMA commands with the same tag, however they cannot be executed concurrently. That is, if the trace contains the events (e s1 , e d1 ) and (e s2 , e d2 ) of two DMA commands with the same tag i then, the termination of one should precede the start of the other, i.e., e d1 (i) ≤ p e s2 (i) or e d2 (i) ≤ p e s1 (i).

A DMA race occurs at runtime when at least two DMA commands operate on the same memory region at the same time, and at least one of the commands operates in write mode on the memory region. In the following, we assume a DMA trace as per Definition 3.

Definition 4 (Overlap in space): Consider two memory regions r = (α, s) and r = (α , s ). Regions r and r are said to overlap in space, noted overlap(r, r ), when:

(α ≤ α < α + s) ∨ (α ≤ α < α + s ).
Their overlapping is another memory region, noted overlapping(r, r ), and is defined as:

(α , α + s -α ) if α ≤ α , (α, α + s -α)
otherwise.

B. Algorithm for Monitoring DMA Races

The proposed algorithm observes the arrival of DMA events and acts as a filter. When a new DMA command arrives and it is racing with another active command, the new command is not executed and is stored, to be released later when it is not racing anymore with any active command. Subsequent DMA commands that have a dependency with a currently suspended DMA command must also be suspended (even if their execution does not induce a race with active commands).

Consider the scenario depicted in Fig. 1 that illustrates the behavior of the proposed monitor over the execution of 3 DMA requests. When the DMA request r 1 is issued, a race is detected with another request (for instance, from another processor) that is currently being executed. Request r 1 is therefore suspended. Assuming request r 3 depends on r 1 , when r 3 is issued, it must also be suspended in order to preserve the causality between DMA commands defined by the program. When a DMA request r 2 is issued, it is not suspended and is executed since it is not racing with any active command nor depends on a suspended command.

We consider 2 forms of dependencies,

• Address Dependency: All DMA requests involving the same or overlapped address space of a currently-executing DMA request depend on it. • Processor Dependency: All DMA requests issued from a processor are considered to be dependent on a currentlyracing DMA request from the same processor. In this case, the dependency order follows the processor sequential order in which the requests are issued.

The Processor Dependency constraint applies in addition to the Address Dependency constraint in order to guarantee a consistent execution of the program. Address Dependency serializes the DMA read/write order operations. Processor Dependency serializes the execution of DMA commands issued from the same processor to follow a sequential execution. More generally, the constraint induced by DMA Dependency can be formalized as follows. When a DMA request r i depends on a request r j , written r i r j , r i must be executed before r j . Therefore, our algorithm must ensure that if r i r j , then e d (r i ) ≤ p e s (r j ) should hold in the output trace.

The proposed monitoring algorithm is described in the sequel. It is triggered each time a DMA start or end event is observed. The algorithm first determines the possible races with active DMA commands through the check race function (line 6). It checks whether the arriving DMA command is racing (in the sense of Definition 6) with any active DMA command and returns the list rl of racing DMA commands tags. If a race is detected (line 15), the execution of this command is deferred and it is added to the list of suspended DMA commands along with its associated list of racing commands. If there is no race with any active commands (line 8), the algorithm checks through the check dependency function if the current/arriving DMA command r c depends on a currently suspended DMA command r s and returns the list depl of depending DMA commands tags. If such a dependency exists, then the current command is also suspended to be released later after the execution of the DMA requests in depl. Otherwise, the new DMA command is added to the list of active commands and is executed (lines 10 and 11).

b) In case of an end event (lines 19 to 37).

• The terminating command is removed from the list of active commands. The lists rl and depl of suspended DMA commands are updated to reflect the termination of a racing or a depending DMA command (lines 21 and 22). • Suspended commands with an empty racing list and an empty dependency list can now be released provided that they do not race with any active command. Therefore the algorithm first computes the set candidates of possible DMA commands to be released (i.e., with an empty racing list and an empty dependency list, line 24). These commands are then removed from the list of suspended DMA commands.

III.IMPLEMENTATION AND EXPERIMENTAL VALIDATION

The monitoring algorithm described in Section II-B has been implemented in a prototype tool. The tool mimics the behavior of a DMA controller. It takes as input an execution trace of DMA commands and applies the algorithm according to the arrival of each DMA start or end event.

In order to provide input traces to the tool, we use Monitoring Algorithm for DMA Races Input: a trace of DMA commands that are possibly racing. Output: a correct and race-free execution trace of DMA commands. if e is a start event then

6:

rl := check race((tag, src, dst, size), active)

7:

if rl = ∅ then 8:

depl := check dependency((tag, src, dst, size), suspended)

9:

if depl = ∅ then 10:

execute(tag)

11:

add active, (tag, src, dst, size)

12:

else (* a dependency detected *)

13:

add (suspended, ((tag, src, dst, size), depl))

20:

for all ( , rl) ∈ suspended do ( , depl) ∈ suspended

21:

remove(rl, tag)

22:

remove(depl, tag)

23:

end for (* Trying now to release some suspended DMA commands *)

24:

candidates := {dma | (dma, ∅) ∈ suspended}

25:

remove(suspended, candidates)

26:

to release := ∅

27:

for all dma ∈ candidates do

28:

if check race(dma, to release ∪ active) = ∅ then

29:

add(to release, dma)

30:

end if

31:

end for

32:

tmp suspended := candidates \ to release

33:

for all dma ∈ tmp suspended do

34:

add suspended, (dma, check race(dma, to release))

35:

end for

36:

output(to release)

37:

add(active, to release)

38:

end if 39: end while some industrial benchmarks of array and image processing, namely increment, the difference between 2 images and FAST, provided by STMicroelectronics as part of STHORM SDK.

In order to produce DMA races, we run a mutated version of these benchmarks where errors, such as synchronization or addressing, on DMA operations have been introduced. These errors are commonly reproduced by programmers during software development. Then, we run the applications on the STHORM platform [START_REF] Melpignano | Platform 2012, a many-core computing accelerator for embedded socs: performance evaluation of visual analytics applications[END_REF] using the cycle-accurate simulation mode. After execution, we extract the DMA events information required as input for the monitoring tool.

Figure 2 shows how the size of the memory space required by the tool for storing active and suspended DMA requests evolve with the arrival of start and end DMA events. The arrival of events is clearly seen with raising and falling edges in the graphs. Note that the arrival of events in the input trace follows some regular pattern where DMA events start (ascending edge) and terminate (falling edge) at regular intervals. This is due to the data parallel regular feature of the considered applications. We plot the results for the following,

• monitored trace: where the monitor is applied to the input trace only for the detection of errors, without any correction.

Memory Overhead.

In all benchmarks, the memory overhead, i.e the required on-chip memory to store active and suspended DMA commands, of both detection and correction mode does not exceed 1.5 KB. This is very important to assess because of the very limited available on-chip memory (in STHORM, 16 KB of TCDM are allocated to the DMA controller and a total of 256 KB is shared between 16 cores). Memory overhead does not depend on the total number of DMA events during the whole execution, but rather on the number of active (concurrent) DMA requests combined with suspended DMA requests. This number varies during execution and the maximal value is negligible (less than 5%) compared to the trace size. Recall that the number of suspended DMA requests when correction is not considered in null. Therefore, in all benchmarks the memory overhead is larger when correction is considered.

b) Execution Time Overhead

The last DMA event marks the total execution of the trace. In the monitored trace, this time is the same total execution time as in the input trace. However, when correction is considered, it is not the case anymore. This is observed on the x-axis where the last event occurs later in the corrected trace than in the monitored one. The difference between the two values represents the execution time overhead induced by rescheduling in the correction. We can clearly see that overhead is very small (less than 2%) with both types of rescheduling (with Address or Processor dependency).

IV. CONCLUSION In this paper, we proposed a monitoring algorithm for the detection and the prevention of DMA races. This allows to build more robust DMA controllers with a better and an automatic control of DMA requests. The algorithm is efficient, and the results obtained experimentally present a good proof of concept that the implemented prototype monitoring tool can be part of a real debugging tool-chain. Indeed, the proposed algorithm has a very cheap memory overhead which mainly depends on the number of active DMA requests because the algorithm runs in an online fashion. The execution time overhead behaves differently according to the traces, however we observe that it is in most cases negligible. This opens an optimistic perspective in being able to avoid dynamically DMA races with almost no delay on the execution time of programs.

Fig. 1 :

 1 Fig. 1: r 1 is suspended due to a DMA race detection, r 3 is also suspended due to a dependency violation. a) In case of a start event (lines 6 to 17).The algorithm first determines the possible races with active DMA commands through the check race function (line 6). It checks whether the arriving DMA command is racing (in the sense of Definition 6) with any active DMA command and returns the list rl of racing DMA commands tags. If a race is detected (line 15), the execution of this command is deferred and it is added to the list of suspended DMA commands along with its associated list of racing commands. If there is no race with any active commands (line 8), the algorithm checks through the check dependency function if the current/arriving DMA command r c depends on a currently suspended DMA command r s and returns the list depl of depending DMA commands tags. If such a dependency exists, then the current command is also suspended to be released later after the execution of the DMA requests in depl. Otherwise, the new DMA command is added to the list of active commands and is executed (lines 10 and 11).

1 :

 1 active := ∅ (* The set of active DMA commands *) 2: suspended := ∅ (* The set of suspended DMA commands *) 3: while not end of trace do 4: wait e(tag, src, dst, size) (* Wait for a new DMA event *) 5:

Fig. 2 :

 2 Fig. 2: Memory and execution time overheads of the monitor when applied to benchmark traces.

  Definition 5 (Overlap in time): Two DMA commands identified by tag and tag are said to be executed concurrently, noted concur(tag, tag ) if: e s (tag) ≤ p e s (tag ) ≤ p e d (tag) ∨ e s (tag ) ≤ p e d (tag) ≤ p e d (tag ). Definition 6 (DMA race): Two DMA commands (tag, srcα, dstα, s) and (tag , srcα , dstα , s ) are racing if they are executed concurrently in the sense of Definition 5 and if two distinct memory regions involved in these commands overlap in space:

		overlap (srcα, s), (dstα , s )	
	concur(tag, tag )∧ 	∨ overlap (dstα, s), (srcα , s )	 .
		∨ overlap (dstα, s), (dstα , s )

•

  The algorithm then computes the set to release (lines 26-31) of DMA commands. It checks for each DMA command in candidates if it is race-conflicting with any active DMA commands. Commands with no race are added to the set to release and can be actually executed. The rest of the commands are stored in the set tmp suspended .• DMA commands in the set tmp suspended are once again stored in the set of suspended DMA commands, but with an updated/recomputed racing list taking into account the DMA commands to be released. These steps are done at lines 33 to 35. • DMA commands to be released are finally validated and become active (line 38).

  • corrected trace with Address Dependencies: it is the monitored trace where correction is applied by deferring Address dependent DMA requests.• monitored trace with Processor Dependencies: it is the monitored trace where correction is applied by deferring Processor dependent DMA requests, in addition to Address dependent requests.

		1,200	monitored	corrected/address	corrected/proc	1,200	monitored	corrected/address	corrected/proc	400			monitored	corrected/address	corrected/proc
		1,000						1,000
	Memory Overhead (bytes)	400 600 800					Memory Overhead (bytes)	400 600 800					Memory Overhead (bytes)	100 200 300
		200						200
		0						0						0
			3.56 3.57 3.57 3.58 3.58 3.59 3.59	3.6	3.6	3.61	3.6	3.65	3.7	3.75	3.8		3.6	3.7	3.8	3.9	4	4.1	4.2	4.3
			Arrival time of DMA events (cycles)		•10 7		Arrival time of DMA events (cycles)	•10 7			Arrival time of DMA events (cycles)	•10 7
			Increment: 1024 DMA commands		(b) Image difference: 1500 DMA commands		(c) FAST: 672 DMA

The block size refers to the quantity of data (in words/bytes) to be transferred.

Acknowledgement

We thank the AST-computing division team at STMicroelectronics, for providing us with the STHORM SDK and the benchmarks for our experiments.


Daniela Andone
email: dana@aii.pub.ro

Fuzzy rule base complexity reduction: a survey

Keywords: complexity reduction, similarity, fuzzy model, semantic based models, data based models. 1

The paper presents a survey of fuzzy rule base reduction techniques. The identification of fuzzy models from training data needs to consider both data fitness and complexity. The methodologies of model design can be mainly divided into two groups: the semantic-driven modelling and the data-driven modelling. The first model design type proposes models which are built based on expert knowledge. However, it is often the case that the model contains redundant rules and /or variables, so there is a need to reduce the redundancy of the model. The second model design type became more popular in the last decade partly due to the fact that fuzzy models were found to be able to approximate with arbitrary accuracy any continuous control function . These models usually use tremendously large number of rules and do not take into account the complexity of the model. This characteristic also emerged the issue of rule base reduction. The present paper summarizes the efforts done on the complexity reduction field.

INTRODUCTION

The research of complexity reduction methods depend on the model design techniques, which can mainly be divided into two groups: the semantic driven modeling and the data driven modeling. In the First category models are build based on expert knowledge and the rule base is set up manually. The Mamdani version of fuzzy model became very popular in practice. This version required much less computational effort because the projection spaces are used instead of the multidimensional product space. The idea of the Mamdani algorithm is to use the heights of the intersections of the observations with the antecedents and weighting the consequents with these, by simply cutting them at the given height. Semantic based models used semantically interpretable fuzzy terms and rules with fuzzy sets as consequents. The rules are usually of Mamdani type [1], with fuzzy sets in the consequents:

: i R If 1 x is 1 i A and…and in x is in A then i B is y
However, it is often the case that the model contains redundant rules and / or variables, so it requires to reduce redundancy in the model. In the last decade data driven fuzzy model design became more popular due to the fact that fuzzy models were found to be universal approximators, capable to approximate with arbitrary accuracy any continous control function. Takagi-Sugeno-Kang (TSK) model type, were the rule consequen are linear function of the inputs, demonstrate the fact that are practically feasible and sufficiently good approximative models for control function approximation [6]: . When searching for the relevant rules for a given input, an exhaustive search among all the rules should be performed. The computational need of the model can be decreased either by decreasing the number of terms, T, or the reduction of the number of variable, k, or both.

: i R If 1 x is 1 i A and…and in x is in A then i i i b x a y   where   in i i a a a ,....

COMPLEXITY REDUCTION OF SEMANTIC BASED MODELS

This section surveys the methods proposed for complexity reduction of rule base designed by semantic driven model. The first method leads to sparse rule bases and rule interpolation, that . was the first introduced by Koczy and Hirota [START_REF] Wang | Fuzy basis functions, universal approximation and orthogonal least-squares learning[END_REF]. The second one, more effective, aims to reduce the dimension of the sub rule bases by using hierarchical fuzzy rule bases.

Rule interpolation

Fuzzy rule interpolation was one of the first approaches to reduce the complexity of fuzzy models. Its main idea is that particular fuzzy rules, which can be substituted by linear interpolation of the neighboring rules, can be omitted from the rule base. Therefore this method aims at reducing T in the rule equation of complexity. Classical fuzzy inference algorithms deal with dense rule-bases, (meaning that for any

X x 

, where X is the input space, at least one of the rules is firing). The if then rule "If x is A then Y is B" is interpreted as: "The more similar is x to A the more similar is y to B". For the case when the rule base is sparse, (the antecedents in the rule base don't cover the input space) different approaches should be used, as for example Koczy-Hirota interpolation, or one of its variants.

The K-H interpolation uses the "horizontal representation" of the fuzzy sets, based on

 cuts, { ] 1 , 0 ( :    A }, where } ) ( : {     x A x A .
A general notion of the degree of similarity was introduced, based on the family of  distances between two convez and normal fuzzy sets, which is defined as

     } 1 , 0 , , { } , { , 1 , 0 ), , ( ) , ( 2 1 2 1 2 1 , 2 1               U U L L C A A A A U L C A A d A A d (2)
subscripts L and U denoting the minimum and maximum of the respective  cuts. Using this notion of distance ( 2), the fuzzy similarity set can be defined as

               1 , 0 , ) , ( 1 }} , { , 1 , 0 ), , ( { ) , ( 2 1 , 2 1 , 2 1     A A d U L C A A s A A s C C (3)
the elements of similarity degree set being the reciprocals of the elements of the distance set. Yhe basic idea of the rule interpolation is formulated in the Fundamental Equation of Rule Interpolation:

) , ( : ) , ( ) , ( : ) , ( 2 1 2 1 B B D B B D A A D A A D      (4)
In this equation (the fuzzy distance family), linear interpolation between corresponding  cuts is performed. A more general from of (4 gives)

  1 , 0 , ) , (           j j B A A S B (5)
where  s is some  cut related similarity degree, e.g., the fuzzy similarity (3) obtained from the reciprocal distances of the  cuts. The Mamdani type algorithms are thus replaced by

        r j j C r j C j j C A A d B A A d B 1 , 1 , ) , ( 1 ) , ( 1     (6)
were the normalized degree of similarity for fixed  and C is reciprocal distance of the observation from the corresponding antecedent, divided by the sum of all these distances.

In conclusion, the KH linear interpolation is such an approach which is able to work on sparse rule bases, and determines the conclusions by its  cuts in such a way that the ratio of distances among the conclusion ad the consequents should be identical wirh the ones among observation and antecedents for all important  cuts. This fundamental equation of KH linear rule interpolation is an extension of the linear interpolation for rule based convex and normal fuzzy sets in accordance with the gradual semantic interpretation, proposed first by Dubois and Prade [9], "the more similar is the observation to an antecedent the more similar the conclusion should be to the corresponding consequent of the given antecedent". The linear interpolation can be applied if: 1. there exists an ordering among the fuzzy sets in each dimension, 2. the observation is located between two antecedents and 3. all involed fuzzy sets are convex and normal. The KH method has a significant drawback: it may produce conclusions which are not interpretable as fuzzy sets. This problem can be solved by using the modified  cuts based method [3].

Hierarchical rule bases

This approach is based on the modification of rule base structure, and thus reduce the exponent k in the expression of complexity. In order to reduce computational complexity, hierarchically structured fuzzy rule bases may be used.

The fuzzy input domain

p X X X X     ... 2 1
is partitioned, so that some variable will belong to the meta-level

p p X X X Z p      0 0 2 1 0 , 
, and the rest to the sublevels. In

0 Z a partition } , , { 2 1 n D D D    can be determined: 0 1 Z D n i i   
and the meta-level rules will look like:

If 0 z is 1 D then use the sub-rulebase i R
While in the lower levels, we deal with the usual type of rules:

If 1 z is ij A then y is ij B
where the first subscript indicates the sub-rule base and the second subscript the number of the rule in the sub-rule base. In each element of  , for example i D , the sub-rule base i R has local validity. In the worst case, each sub-rule base refers to exactly

p p X X X Z X     0 0 / inputs.
The hierarchical approach does not improve the . The main problem of the method is that it is often difficult to determine a proper partition of the state space so that in the elements of the partition some variables can be omitted. There are attempts to combine hierarchical and sparse rule bases [4], which could lead to simultaneously reduce the base T and the exponent k in the expression of complexity

  k T O .

COMPLEXITY REDUCTION OF DATA BASED MODELS

Orthogonal least squares-based techniques

The orthogonal least squares (OLS) method was first applied to fuzzy systems in [5], to select the most important fuzzy basis function needed to approximate a data set. Considering N input-output data pairs

M i y y p p g err T i T i i i    1 , ] [
This ratio offers a simple means of ordering the rule. The OLS method transforms he column of the firing matrix W into a set of orthogonal basis vectors in order to inspect the individual contribution of each rule. The main advantage of OLS method is that the user can select the required number of rules based on the approximation accuracy of he relative contribution of the selected rules.

Singular value besed decomposition

Fuzzy logic inference system are suffering from exponentially growing computational complexity in respect to their aprproximation property. The main goal of introducing fuzzy rule base complexity reduction techniques is enhancing the universal approximation property of the fuzzy inference by extending the number of antecedent set while the computational complexity is kept relatively low. Singular value based decomposition (SVD) based fuzzy approximation technique was initiated by Yam [7], which directly fimds a minimal rule-base from sampled values. Shortly after, this concept was introduced as SVD fuzzy rule base reduction and structure decomposition. Its key idea is conducting SVD of the consequents and generating proper linear combinations of the original membership functions to form new ones for the reduced set. An extension to multidimensional cases may also be conducted in a similar fashion as the Higher Order SVD (HSVD) reduction technique proposed in [8]. The key idea of using SVD in complexity reduction is that the singular values can be applied to decompose a given system and indicate the degree of significance of the decomposed parts. Reduction is conceptually obtained by the truncation of those parts, which have weak or no contribution at all to the output, according to the assigned singular values. This advantageous feature of SVD is used in Yams works to extract a given model approximation and discard those rules which have no significant role in the overall system according to a given apprixiation accuracy. Let an L-variable rule base given with the following rules: : ,....,

1 N i i R If 1 x is 1 , j a A and …. N x is N j N A , then y is N i i B ,... 1
. Applying TS-model the output is calculated as:

          1 1 2 2 1 1 1 1 ,..., 1 , ) ( ) ( I i I i I i N n i n i n N N N n y x w x f y  (8)
,      n n i i S S when    and (2)
ordering:

n n n n I i i i S S S      ...
  2 1 1 ) ( ˆ       N n R I i n i n n n n B B  ( 11
)
This property is the higher-order equivalent of the link between the SVD of a matrix and its best approximation in a least-squares sense.

If a rule base is given by tensor B and vectors

) ( n n x w
, its complexity can be minimized via executing HISVD on B as:

) ) ( ( ) ( ) ( ) ( 1 1 11 1 n n n N n n n N n n N n n n N n U x w S x w U S x w B x f y                   
If singular values are discarded the size of S and n U Decreases. Let's denote as

CONCLUSIONS

This paper gives a brief survey of complexity reduction techniques. The motivation of this topic is that ihe identification of fuzzy models and controllers from training data needs to consider an important feature between data fitness and complexity. The importance of this feature is pointed out by the fact that fuzzy models and controllers with large number of local models may encounter the risk of having an approximation capable of fitting training data well, but incapable of running n low satisfactory computational cost. In order to help the developments of fuzzy models and controllers to strive for balance between the two conflicting design objectives, this paper survey various fuzzy model reduction techniques.

  firing strength of the jth rule. The equation (1) offers a way to handle the problem by classical numerical methods. Fuzzy model have exponential complexity. If a fuzzy model contains k variables and maximum T fuzzy terms in each dimension, the order of the number of necessary rules is   k T O

.

  and A is an upper-triangular matrix, substituting W=PA in ec. (7) and using he fact that columns i p of P are orthogonal, the sum of squares of y(k) can be written as: An error reduction ratio due to an individual rule i can be determined:

  -th antecedent function on the n-th input universe. Equation (8) can be described in tensor-product form:

  S equal to zero. Then:

B

  is less than B if singular values are discarded hence the rule base is reduced.


Abdeljalil Saghe

The field of Omicran-reals A new approach to nonstandard analysis

Keywords: Nonstadard analysis, hyppereals, Abraham Robinson, Internal set theory, infinitesimal

Introduction

In 1961 Abraham Robinson [START_REF] Robinson | Non standard analysis[END_REF] showed how infinitely large and infinitesimal numbers can be rigorously defined and used to develop the field of non-standard analysis. To understand his theory nonconstructively, it's necessary to use the essential proprieties given by the model theory and mathematical logic.

After the birth of this new theory, more mathematicians have found the important applications of the nonstandard analysis in physic [START_REF] Bagarello | Nonstandard Analysis in Classical Physics and Scattering[END_REF][START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF][START_REF] Fittler | Asymptotic nonstandard quantum electrodynamics[END_REF], numerical analysis and variational methods [START_REF] Bagarello | Nonstandard variational calculus with applications to classical mechanics. I. An existence criterion[END_REF][START_REF] Bagarello | Nonstandard variational calculus with applications to classical mechanics. II. The inverse problem and more[END_REF].

In 1977 a new axiomatic representation of hyperreals is given by Edward Nelson [START_REF] Nelson | Internal Set Theory : a new approach to Nonstandard Analysis[END_REF], in the sense to simplify the Robinson's method, he proposed to add three axioms on the set theory and obtained a new theory called internal set theory [START_REF] Nelson | Internal Set Theory : a new approach to Nonstandard Analysis[END_REF].

From the construction of Robinson we can see every hyperreal as an element of R N modulo a maximal ideal M, the ideal M is defined with a non principal ultrafilter U, the existence of U is proved by the axiom of choice, by using the ultrafilter U we define the order relation in the field of hyperreals. Unfortunately, we can't determine exactly this order relation because the ultrafilter is unknown.

Our aims in this article is to give a new field which contains the infinite and infinitesimal numbers, without using the properties of model theory, and witout adding the new axioms to ZFC ( Zermelo-Frankel+Axiom of choice ). The new approach is very simple and we can determine precisely the order relation defined on the new field. The new field is noted O and called field of Omicran-reals.

In this paper we restart in the section of preliminary results by some notions to define the infinitesimal and infinite numbers. In the section 3, we construct a new unitary ring by using a strict subset of R N . After we define a ideal I of the above ring which maximal, and we deduce that the quotient of this ring by I is a new field. Finally, we construct the new field of Omicranreals which is a totally ordered field and a extension of R.

Preliminary results

Let H(D(0, ε)) the set of the holomorphic functions on the disk D(0, ε). * corresponding author: saghe007@gmail.com Therem 1 If h is a holomorphic fuction on the disk D(0, ε), and h(0) = 0 then : h(z) = z k g(z) on a neighborhood of 0, where k is a non-zero integer, and g ∈ H(D(0, ε)) and g(0) = 0.

Therem 2 The zeros of a nonconstant analytic function are isolated.

Definition 1 We define the following assertions :

• A totally ordered set (E, ) is called a ordered R-extension if R ⊆ E ; x y ⇔ x ≤ y ∀(x, y) ∈ R 2 . • In addition if (E, +) is a commutative group, we consider |α| = max(α, -α) = α , when -α α, -α , when α -α.
• We note x ≺ y while : x y and x = y.

• Let the set I E be defined as follows

I E = {α ∈ E / 0 ≺| α |≺ ε ∀ε ∈ R + * }. I E is a set of infinitesimals.
Remark 1 If it has not ambiguity we replace the symbol by ≤ , and ≺ by <.

To construct the new extension of R which contains the infinitesimals, it's sufficient to prove the following theorem :

Therem 3 There exist a extension field (E, +, .) of (R, +, .), and partiel order ≤ such that:

(E, ≤) is a ordered R-extension and I E = ∅. Remark 2 An element δ of I E = ∅ is called infinitesimal.
3 Construction of a new extension of the reals

The metalic map

Let D(0, 1) (resp.D ′ (0, 1)) the open (resp.closed ) disk of radius 1 and centre 0.

Definition 2 Let u be a map from ]0, 1] to R, such that :

• There exists a map u is defined on D ′ (0, 1), and holomorphic in a neighborhood of 0.

• There exists ε > 0, such that ∀x ∈]0, ε[ we have a :

u(x) = u(x).
The u is called a metalic map, and u is a metalic extension of u.

Example 1 If f is defined in an interval ]0, 1] as : f (x) = 2x + 1 when x ∈]ε, 1], 1 -3x 2 when x ∈]0, ε] then a metalic extension f is given by : f (z) = 1 -3z 2 in the disk D ′ (0, 1).
Remark 3 If u is metalic, then the two metalics extension u and u of u are identic in a disk D(0, ε) from the theorem 2.

Definition 3 We note ∆ 1 = { u, u is a metalic map }, and we have the following definitions :

• ∆ 1 ( 1 n ) = { u( 1 n ) n≥1
, u is a metalic map }. • H 0 = the set of maps u defined on the disk D ′ (0, 1) and holomorphic in a neighborhood of 0.

• (H 0 , +) is a commutative group, let O 0 be a subgroup of H 0 containing the maps defined on the disk D ′ (0, 1) and are zero in a neighborhood of 0.

• Let θ 0 be a map defined as :

θ 0 : ∆ 1 ( 1 n ) -→ H 0 /O 0 u( 1 n ) n≥1 -→ C( u) which C( u) is the equivalence classe of u modulo O 0 .
The map θ 0 is a well-defined from the unicity of C( u).

• We consider the surjective map θ 1 defined as :

θ 1 : ∆ 1 ( 1 n ) -→ θ 0 (∆ 1 ( 1 n )) u( 1 n ) n≥1 -→ C( u)
and the set :

∆ 1 ( 1 n ) = { θ -1 1 (C( u)) , C( u) ∈ θ 0 (∆ 1 ( 1 n )) }. • We define on the set ∆ 1 ( 1 n ) the following equivalence relation ∼ : u( 1 n ) n≥1 ∼ v( 1 n ) n≥1 ⇐⇒ ∃n 0 , ∀n ≥ n 0 , u( 1 n ) = v( 1 n ). • u( 1 n ) n≥1 is the equivalence classe of u( 1 n ) n≥1 modulo ∼.
Remark 4 1. We can check the equality:

u( 1 n ) n≥1 = θ -1 1 (C( u)). Then : ∆ 1 ( 1 n ) = u( 1 n ) n≥1 , u ∈ ∆ 1 .
2. The sets ∆ 1 and ∆ 1 ( 1 n ) are commutative groups. 3. The map defined as :

θ 1 : ∆ 1 ( 1 n ) -→ E 1 = θ 0 (∆ 1 ( 1 n )) u( 1 n ) n≥1 -→ C( u) is an isomorphism between two groups. Definition 4 • A 2 = 1 u , u ∈ ∆ 1 ∀x ∈]0, 1] u(x) = 0 and lim u( 1 n ) = 0 . • ∆ 2 = v / v :]0, 1] -→ R, there exists 1/u ∈ A 2 and ε > 0 such that v /]0,ε] = ( 1 u ) /]0,ε] . • ∆ 2 ( 1 n ) = (v( 1 n )) n≥1 , v ∈ ∆ 2 .

Construction of a unitary ring

Lemma 1 Let ∆ = ∆ 1 ∪ ∆ 2 , (∆, +, .
) is a unitary ring.

Proof.

• The stability of the sum : The set ∆ is non-empty set, because ∆ 1 = ∅ and R ⊆ ∆ 1 (we identify the constant fonctions by the real numbers ). Show that : ∀g ∈ ∆, and h ∈ ∆ then g + h ∈ ∆.

First case : if (g, h) = (u, v) ∈ ∆ 2 1
, we verify that the function s = f + g is matalic map, and :

s = u + v. Second case : if (g, h) ∈ ∆ 2 2 , there exists (u, v) ∈ ∆ 2 1 such that lim u( 1 n ) = lim v( 1 n ) = 0 and u(x)v(x) = 0 for every x ∈]0, ε], for ε > 0 small enough, in addition : g /]0,ε] = 1 u /]0,ε] and h /]0,ε] = 1 v /]0,ε]
. Since u and v are holomorphic functions on a neighborhood of 0, there exists (m, n, l) ∈ N 3 such that :

u(z) = z n b 1 (z), v(z) = z m b 2 (z) and u(z) + v(z) = z l b 3 (z). where b 1 , b 2 , b 3 are 3 holomorphic functions on a neighborhood of 0, such that : b 1 (0)b 2 (0)b 3 (0) = 0. Let : ψ(x) = u(x)v(x) u(x) + v(x)
.

The map g + h is defined in the interval ]0, 1], for ε > 0 small enough, and b 1 (z)b 2 (z)b 3 (z) = 0 in the disk D(0, ε), we have :

g(x) + h(x) = 1 u(x) + 1 v(x) = 1 ψ(x) = x l-m-n b3(x) b1(x)b2(x) , for every x ∈]0, ε]. If l -m -n ≥ 0, The map defined as φ(z) = z l-m-n b3(z) b1(z)b2(z) in D(0, ε) 1 if not is a metalic extension of g + h, then g + h is a element of ∆ 1 .
1. We assume that g, h ∈ ∆ 1 . From the Intermediate value theorem we deduce that there exists

β k ∈| 1 n k , 1 n ′ k
| such that (gh)(β k ) = 0, (we can choose the β k so that the sequence (β k ) is strictly decreasing), then the holomorphic function gh has an infinite number of roots in neighborhood of 0, from the theorem2, we deduce that the function gh is the zero function, then g = h, which is absurd.

2. Now, we suppose that g, h ∈ ∆ 2 . There exists (u, v) ∈ ∆ 2 1 , such that : u /]0,ε] = ( 1 g ) /]0,ε] and v /]0,ε] = ( 1 h ) /]0,ε] . from the above results, we deduce that : u(δ) ≤ v(δ) ou v(δ) ≤ u(δ). which implies that: g(δ) and h(δ) are comparable.

3. In the case of g ∈ ∆ 1 and h ∈ ∆ 2 . There exists h 1 ∈ ∆ 1 and ε > 0, such that: h /]0,ε[ = ( 1 h1 ) /]0,ε[ . Since h 1 is a metalic function, then the sequence (h 1 ( 1 n )) keeps a contant sign from a certain rank, in fact: if it's not the case, then ∀k ∈ N there exists

n k > k et n ′ k > k such that: h 1 ( 1 n k ) > 0 and h 1 ( 1 n ′ k ) < 0.
From the Intermediate value theorem we deduce that there exists

β k ∈| 1 n k , 1 n ′ k
| and (h 1 )(β k ) = 0, (we can choose the β k such that the sequence (β k ) is strictly decreasing), from the theorem2, h 1 is the zero function on the neighborhood of 0, which absurd( because we suppose (h 1 ( 1 n )) does not keep a constant sign from a certain rank) Finally, we deduce that the sequence

(h 1 ( 1 n )) keeps a constant sign, since lim h 1 ( 1 n ) = 0, then lim 1 h1( 1 n ) exists, and lim 1 h1( 1 n ) = ±∞, which implies lim h( 1 n ) = ±∞. -if lim h( 1 n ) = +∞, then g(δ) ≤ h(δ) ( because g( 1 n ) ≤ h( 1 n ), from a certain rank ). -if lim h( 1 n ) = -∞, then h(δ) ≤ g(δ) ( because h( 1 n ) ≤ g( 1 n
), from a certain rank ). • Now, it remains to show that:

I O = ∅.
For that, it is necessary to find a element δ ∈ O which infinitesimal. for u : x -→ x, we have u ∈ ∆ (more precisely ∆ 1 ) and δ = u(δ) = u( 1 n ) n≥1 . In addition, we have : 0 < δ < ε for every real strictly positive ε, because there exists p ∈ N such that: 0 < u( 1 n ) < ε, for every integer n > p. Then δ is infinitesimal.

Conclusions 1 Finally, we deduce that:

• (O, +, .) is a extension field of (R, +, .).

• (O, ≤) is a ordered R-extension, which contains the infinitesimal element δ.

The field (O, +, .) is called a field of Omicran-reals.

If m + nl < 0, the map defined as : ψ(z) = z m+n-l b1(z)b2(z) b3(z) in D(0, ε)

if not is a metalic extension of ψ, in addition lim ψ( 1 n ) = 0, we deduce that the is g + h is a element of ∆ 2 .

Third case : If (g, h) ∈ ∆ 1 × ∆ 2 , there exists (u, v) ∈ ∆ 2 1 , such that : g = u , h /]0,ε] = 1 v /]0,ε] , lim v(

Let k(z) = v(z) u(z) v(z) + 1 .

Since v(0) = 0, we have k(0) = 0, and k is a holomorphic function in a disk D(0, ε), for ε > 0 small enough. The map k is nonzero and holomorphic at z = 0, we can choose the ε so that k(x) = 0 for every x ∈]0, ε].

Let φ the function defined in ]0, 1] as :

We verify that :

Finally, we deduce that (∆, +) is a commutative group.

• Now, we can show the stability of the law (.) in ∆, for that, we distiguish tree cases :

1. We can easily verify that the product of two metalic functions is a metalic function.

In this case, we assume that g ∈ ∆ 1 and h ∈ ∆ 2 , we can show that gh ∈ ∆, in fact, there exists

-if lim u( 1 n ) = 0, then v u is holomorphic in the disk D(0, ε), which implies that :

3. In the case of g ∈ ∆ 2 and h ∈ ∆ 2 , we verify easily the stability of the law (.). Finally, we deduce that (∆, +, .) is a commutative and unitary ring, where the constant function 1 ∆ is a multiplicative identity of ∆.

Construction of the new field

Let I 0 the set defined as :

it is a set of maps defined in ]0, 1], and zero on ]0, ε] ( for 0 < ε ≤ 1 ).

Thus, we have demonstrated the following proposition.

Proposition 1 I 0 is a maximal ideal of ∆.

Therem 4

The ring (∆/I 0 , +, .) is a field.

Proof.

From the above proposition, the ideal I 0 is maximal, so we deduce that the ring (∆/I 0 , +, .) is a field.

The field of Omicran-reals

We consider the set defined as

The equivalence class is given by : g(

) is a field.

θ is an isomorphism.

Therem 5 There exists a set O and a total order ≤ such that :

) is an extension field of (R, +, .).

Proof.

The set ∆/I 0 is noted ∆ 0 , we replace C(g) = g by g ( if it has not ambiguity ). From what precedes, we deduce that the map :

Let δ an indeterminate, and O = ∆ 0 (δ) = { g(δ) , g ∈ ∆ 0 }. The map defined as :

is a ring isomorphism. Then (O, +, .) is a field, in addition, the map ϕ = δ * • θ defined as :

• for g = cste = l, we note l = (g( 1 n )) n≥1 , we identify l by the image of l by ϕ, and we find ϕ(l) = l. by using the identification, we deduce that : R ⊆ O.

• We can define on O the following relation ≤ :

g(δ) ≤ h(δ) if and only if there exists an integer n 0 , such that : g( 1 n ) ≤ h( 1 n ) for every n ≥ n 0 . It is easy to check that ≤ is reflexive, transitive and antisymmetric, then it is a partial order.

• To show that set (O, ≤) is ordered R-extension, we must show that relation ≤ is total.

For that we consider g, h ∈ ∆ 0 , we assume that these propositions are true ( not g(δ) ≤ h(δ)) and ( not h(δ) ≤ g(δ)).

Next, we need to find a contradiction. If the above propositions are true, then : ∀k ∈ N, ∃n k > k and ∃n

).


Aaron Herman
email: aherman@ncsu.edu

Elias Tsigaridas
email: elias.tsigaridas@inria.fr

Bounds for the Condition Number of Polynomials Systems with Integer Coefficients

Polynomial systems of equations are a central object of study in computer algebra. Among the many existing algorithms for solving polynomial systems, perhaps the most successful numerical ones are the homotopy algorithms. The number of operations that these algorithms perform depends on the condition number of the roots of the polynomial system. Roughly speaking the condition number expresses the sensitivity of the roots with respect to small perturbation of the input coefficients. A natural question to ask is how can we bound, in the worst case, the condition number when the input polynomials have integer coefficients? We address this problem and we provide effective bounds that depend on the number of variables, the degree and the maximum coefficient bitsize of the input polynomials. Such bounds allows to estimate the bit complexity of the algorithms that depend on the separation bound, like the homotopy algorithms, for solving polynomial systems.

Introduction

The study of algorithms for solving polynomial systems are in the center of study of computational algebra and computational mathematics in general. In this context, it is of great importance to define measures of hardness to express the difficulty to compute the solutions of a polynomial system. By "compute" we mean to approximate, up to any desired precision, one or all the roots of a polynomial system.

The condition number of the roots of a polynomial system could be considered, among other things, as such a measure of hardness. It expresses the sensitivity of the roots of a polynomial system, when we allow perturbations in the coefficients of the input polynomials. We refer to the fundamental work of Shub and Smale [START_REF] Shub | Complexity of bezout's theorem: Iii. condition number and packing[END_REF], see also [START_REF] Blum | Complexity and Real Computation[END_REF], or to the recent book of Bürgisser and Cucker [START_REF] Bürgisser | Condition: The geometry of numerical algorithms[END_REF] for a detailed exposition. The complexity of numerical algorithms for polynomial system solving depends on the condition number. Among these numerical algorithms, the most successful, in theory and in practice, are the homotopy methods, e.g. [START_REF] Bürgisser | Condition: The geometry of numerical algorithms[END_REF][START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF].

When the coefficients of the input polynomials are rational numbers, then besides the number of variables and degree of the polynomials, we have one more input parameter; the bitsize of the coefficients. We consider the maximum bitsize of the coefficients of a polynomial as the bitsize of the polynomial. Then, we should be able to express or to bound the measure of hardness for solving a polynomial system, or especially the condition number of the roots, with respect to these three parameters. That is to provide effective bounds as a function of the number of variables, the degree, and the bitsize of the input polynomials [START_REF] Malajovich | Condition number bounds for problems with integer coefficients[END_REF].

From a, first glance completely, different point of view, when the input coefficients are rational numbers, then a fundamental question of great importance is the following: What is the number of bits up to which we need to approximate the roots of a polynomial system, to distinguish them from each other? Can we provide such a bound as a function in the number of variables, the degree, and bitsize of the polynomials? Separation bounds, that is lower bounds on the minimum distance between the isolated roots of a polynomial system provide an answer to this question, in the worst case. We refer the reader to the DMM bound [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF], that is the best known such bound. It is a natural question to ask if the bounds on the condition number and the separation bounds are connected. We will provide a positive answer to this question.

Our results

We consider the problem of bounding the condition number of the roots of square-free univariate polynomials and 0-dimensional polynomial systems with a smooth zero set, when the input polynomials have integer coefficients. We also introduce an aggregate version of the condition number and we prove bounds of the same order of magnitude as in the case of the condition number of a single root.

In the univariate case we improve the currently known bounds [9, Theorem 2.4] by a factor of d (Proposition 1), where d is the degree of the polynomial. For the multivariate case the previous bounds [9, Theorem 2.5], which like ours are single exponential with respect to the number of variables, do not specify the constant in the exponent. We provide precise bounds (Theorem 1) and our approach leads to better bounds than the ones we can obtain by performing the calculations using the previously known approach [START_REF] Malajovich | Condition number bounds for problems with integer coefficients[END_REF]. The exact constants in the exponents can be useful in many applications e.g. [START_REF] Basu | Bounding the radii of balls meeting every connected component of semi-algebraic sets[END_REF][START_REF] Hansen | Exact algorithms for solving stochastic games[END_REF][START_REF] Hansen | Winning concurrent reachability games requires doubly-exponential patience[END_REF]. Such bounds are also needed to establish a connection between Turing machines and the Blum-Cucker-Shub-Smale model and to certify and analyze the Boolean complexity of algorithms based on homotopy techniques [START_REF] Beltrán | Robust certified numerical homotopy tracking[END_REF].

The aggregate versions of the condition numbers we introduce (Proposition 2 and Theorem 2) encapsulate the condition number of all the roots. Contrary to what is expected as a bound in this case, that is the number of roots times the worst case bound for the condition number at a single root, our aggregate version saves a factor equal to the number of roots. As a consequence, in the multivariate case, we gain a factor of d n , where d is the degree of the polynomials and n the number of variables.

Notation

In what follows O B , resp. O, means bit, resp. arithmetic, complexity and O B , resp. O, means that we are ignoring logarithmic factors. For a polynomial

A = d i=0 a i x i ∈ Z[x], deg(A) = d denotes its degree. We consider the height function H(•) which is defined as follows. If a ∈ Z then H(a) = |a|. For a, b ∈ Z, H( a b ) = max{H(a), H(b)}. For a polynomial A, we have H(A) = max k |a k |. Finally, for a matrix M ∈ Z n×n , H(M ) = max i,j |M i,j |. The logarithmic height is defined as h(•) = lg H(•), where lg(•) is the logarithm of base 2. The Mahler bound (or measure) of A is M (A) = a d |α|≥1 |α|
, where α runs through the complex roots of A, e.g. [START_REF] Mignotte | Mathematics for Computer Algebra[END_REF][START_REF] Yap | Fundamental Problems of Algorithmic Algebra[END_REF].

If A ∈ Z[x] and H(A) = 2 τ , then M (A) ≤ A 2 ≤ √ d + 1H(A) = 2 τ √ d + 1.
2 Condition number for univariate polynomials

Let A = d k=0 a k X k ∈ C[X]
and α be one of its roots. The condition number of A at α is defined as follows

µ(A, α) = d i=0 |α| 2i 1 2 |A (α)| ( 1
)
where A is the derivative of A. We define the condition number of A as

µ(A) = max α∈C A(α)=0 µ(A, α) (2)
If A is a square-free integer polynomial such that H(A) = 2 τ , Malajovich [START_REF] Malajovich | Condition number bounds for problems with integer coefficients[END_REF] provided the following bounds for the condition number at a root α,

µ(A, α) ≤ 2 2d 2 -2 d 2d 2 2τ d 2
which in turn leads to the following estimation for the condition number of A

µ(A) = 2 O(τ d 2 ) , or lg( µ(A) ) ∈ O(τ d 2 ).
The following proposition improves this bound by a factor of d.

Proposition 1. Consider the square-free polynomial A = d i=0 a i X i ∈ Z[X] with H(A) ≤ 2 τ and a 0 = 0. Let α = 0 be a root of A. Then µ(A, α) ≤ √ d + 1 15d+1 2 15dτ +τ +18d lg(d) .
Hence lg(µ(A)) ∈ O(dτ + d lg(d)).

Proof: First we bound the numerator of formula (1) as follows

( d i=0 |α| 2i ) 1 2 = (1, α, . . . , α d ) 2 = √ d + 1 (1, α, . . . , α d ) ∞ ≤ √ d + 1 2 d H(A) d
(3) To bound the denominator we need the following result, e.g. [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]. For A ∈ Z[X], let Ω be a set of k pairs of indices of non-zero roots of A.

Then (i,j)∈Ω |α i -α j | ≥ d -18d (d + 1) -15d/2 H(A) -15d ≥ 2 -30d lg d H(A) -15d .
Using the previous bound we can bound A (α). We notice that

|A (α)| = |a d γ =α f (γ)=0 (α -γ)| ≥ γ =α f (γ)=0 |α -γ| ≥ 2 -30d lg d H(A) -15d as |a d | ≥ 1. Finally, by combining the equations µ(A, α) = d i=0 |α| 2i 1 2 |A (α)| ≤ 2 2d H(A) d 2 30d lg d H(A) 15d ≤ 2 32d lg d H(A) 16d ≤ 2 O(dτ +d lg d) = 2 O(dτ ) .
The condition number of A, Eq. ( 2), expresses the maximum condition of all the roots. Hence, one might suggest that if we are interested in a notion of the condition number that accounts for all the roots, then we have to multiply the worst case bound by their number; in our case d. However, it turns out that this is not the case. We consider the following aggregate version of the condition number

μ(A) = d i=1 µ(A, α i )
where {α i } 1≤i≤d is the set of roots of f . We prove that a bound similar to the one of Proposition 1 holds for μ.

Proposition 2. Consider the square-free polynomial

A = d k=0 a k X k ∈ Z[X] with H(A) = 2 τ . Then μ(A) ≤ √ d + 1 2d 2 τ d .
Hence lg( μ(A) ) ∈ O(dτ + d lg(d)).

Proof: We obtain the bound using the properties of the Mahler measure and the discriminant, disc(A).

μ(A) = d i=1 µ(A, α i ) = d i=1 ||(1, α i , . . . , α d i )|| 2 |A (α i )| = d i=1 ||(1, α i , . . . , α d i )|| 2 a d j =i |α i -α j | = d i=1 ||(1, α i , . . . , α d i )|| 2 a d d i =j |α i -α j | = d i=1 ||(1, α i , . . . , α d i )|| 2 a d d |disc(A)| a 2d-2 d = a d-2 d d i=1 ||(1, α i , . . . , α d i )|| 2 |disc(A)| ≤ a d-2 d d i=1 √ d + 1||(1, α i , . . . , α d i )|| ∞ |disc(A)| = a d-2 d √ d + 1 d d i=1 ||(1, α i , . . . , α d i )|| ∞ |disc(A)| = a d-2 d √ d + 1 d d i=1 max{1, |α i | d } |disc(A)| = a d-2 d √ d + 1 d d i=1 max{1, |α i |} d |disc(A)| = √ d + 1 d a 2 d a d d i=1 max{1, |α i |} d |disc(A)| = √ d + 1 d a 2 d (M(A)) d |disc(A)| ≤ √ d + 1 d a 2 d (||A|| 2 ) d |disc(A)| ≤ √ d + 1 d a 2 d √ d + 1 H(A)) d |disc(A)| = √ d + 1 2d a 2 d H(A) d |disc(A)| ≤ √ d + 1 2d H(A) d .

Condition number for polynomial systems

In this section we generalize the bounds of Propositions 1 and 2 to the case of polynomial systems. The definition of the condition number of a root of a polynomial system is given in equation ( 4). We assume that the polynomial systems are 0-dimensional and their zero set is smooth, that is the Jacobian of the system is invertible. First we need to introduce additional notation, which follows closely [START_REF] Beltrán | Robust certified numerical homotopy tracking[END_REF]. Let H n d be the vector space of homogeneous polynomials in n + 1 variables, X 0 , X 1 , . . . , X n , of degree d.

If f ∈ H n d then f = |α|=d f α X α = |α|=d f α X α0 0 X α1 1 • • • X αn n .
For f, g ∈ H n d we consider the following inner product

f, g = |α|=d f α g α d α -1 = |α|=d f α g α d α 0 , α 1 , . . . , α n
and the corresponding norm

f 2 b = f, f = |α|=d |f α | 2 d α -1
.

We consider f = (f 1 , . . . , f n ) ∈ H n d1 × • • • × H n dn =
H to be a 0-dimensional polynomial system of n homogeneous equations in n + 1 variables, with a smooth zero set. For a system of equations, f , we have the following definition of the norm

f 2 = n i=1 f i 2 b .
The condition number of a polynomial system f at a number z ∈ C n is defined in [START_REF] Blum | Complexity and Real Computation[END_REF] as

µ(f , z) = f (Df (z)| z ⊥ ) -1 Diag( z di-1 d 1/2 i ) . (4)
However, to bound the various quantities that appear we use an equivalent definition, Eq. ( 5), from Malajovich [START_REF] Malajovich | Condition number bounds for problems with integer coefficients[END_REF]. Moreover, we follow the notation from [START_REF] Beltrán | Robust certified numerical homotopy tracking[END_REF] to bound condition number of a polynomial system of polynomials having integer coefficients. In this case we assume that H(f i ) ≤ 2 τ for all i.

Let f ∈ H be a polynomial system and let z ∈ P(C n+1 ). Let χ 1 = χ 1 (f , z) defined by

χ 1 = Df (z) z * -1      √ d 1 f z d1-1 . . . √ d n f z dn-1 z      = M -1 1 •M 2
(5) Note that these formulas do not depend on the representative of z and thus are well defined. Their value is also invariant under multiplication of f by a non-zero complex number λ ∈ C. Our goal is to estimate a bound for χ 1 (f , ζ), where ζ is a root of f .

Recall that for any matrix M it holds M ≤ M F . The second norm is the Frobenius norm, that is M F = i,j |M 2 i,j |. First we consider bounds for the norm of M 2 . To bound f , assuming H(f i ) ≤ 2 τ , we proceed as follows:

f = n i=1 f i 2 b ≤ n k=1 2 2τ +d k lg(nd k ) ≤ 2 τ +d lg(nd) . ( 6
)
To bound ζ we use the DMM bounds [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]. The DMM is defined for sparse systems but we can also use it for the homogeneous case. To see this notice that we consider all the possible dehomogenizations of the system and we apply to each of them DMM. Then we take the worst bound.

For any root ζ = (ζ 0 , ζ 1 , . . . , ζ n ) of the system it holds [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]Cor. 4] lg( max

0≤k≤n |ζ k |) ≤ 1+ n i=1 d i + n i=1 j =i d i (τ +lg(2 d n i )) = η 1 = O(d n +nd n-1 τ +n 2 d n-1 lg d).
(7) Now we are ready to bound M 2 by combining equations ( 6) and [START_REF] Hansen | Exact algorithms for solving stochastic games[END_REF]. The bound is as follows:

M 2 2 F ≤ n i=1 d i f ζ di-1 2 + ζ 2 ≤ 2 2τ +3d lg(nd)+d η1 , which simplifies to lg M 2 F ≤ O(d n+1 + nd n τ + n 2 d n lg d) = O(d n+1 + d n τ ). (8)
To bound M -1

1 it suffices to bound M 1 . It holds M -1 1 ≤ n n H(M 1
), e.g. [9, Lemma 4.5]. To obtain a bound for H(M 1 ), first we need an estimation on the evaluation of the derivatives G i,j (X) = ∂ ∂Xj f i (X) at the roots of the system, ζ. Let f

(i,j) n+1 (X, Y ) = Y -G i,j (X)
) and consider the polynomial system

(Σ i,j ) {f 1 (X) = • • • f n (X) = f (i,j) n+1 (X, Y ) = 0}. (9)
This is a system in n + 1 equations in n + 1 variables. It holds deg(f

(i,j) n+1 ) = deg(G i,j ) ≤ d i -1 and H(f (i,j) n+1 ) = H(G i,j ) ≤ d H(f i ) ≤ τ + lg d i .
The resultant of (Σ i,j ) that eliminates the variables X 1 , . . . , X n , is

R i,j = Res d1,...,dn (f 1 (X), . . . , f n (X), y -G i,j (X)) ∈ Z[y]
where R i,j ∈ Z[Y ]. The roots of R i,j correspond to the evaluations of G i,j at the roots of the system f = 0. Therefore, an upper bound on the roots of R i,j provides an upper bound on the evaluation. We should notice that R i,j is not identically zero.

Hence, to obtain the required bounds we can consider the system (Σ i,j ). From this point of view we need to provide lower bounds on the coordinates of solutions of the system. For this we use DMM [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]Thm. 3 and Cor. 4] directly.

First, we need to define (bound) various quantities, see [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]Eq. (3)]. The mixed volume(s)

M 0 = d 1 • • • d n (d i -1) ≤ d n (d-1) ≤ d n+1 , M k = d 1 . . . d k-1 d k+1 • • • d n (d i - 1) ≤ d n-1 (d -1) ≤ d n for 1 ≤ k ≤ n, and M n+1 = d 1 • • • d n ≤ d n ;
and the integer coefficients that appear in the resultant polynomial

= n+1 k=1 (#Q k ) M k ≤ 2 n+1 k=1 Mi n i=1 d nM k k (d i -1) nMn+1 ≤ 2 2nd n d 2n 2 d n .
Finally, we bound the weighted heights of the input polynomials

C = n+1 k=1 H(f k ) M k ≤ 2 (n+lg d) τ d n .
An isolated root of the system with Y coordinate equal to y follows the bound |y| ≤ 2 M0 C. Thus

|G i,j (ζ)| ≤ 2 M0 C ≤ 2 d n+1 +8n 2 d n lg d+(n+lg d)τ d n
for any i, j and for any root ζ of the system. For ζ * it holds that H(ζ * ) ≤ H(ζ) and so we can use the bound from [START_REF] Hansen | Exact algorithms for solving stochastic games[END_REF]. Putting all these together we have the bound

H(M 1 ) ≤ 2 η2
where

η 2 = O(d n+1 + n 2 d n lg d + (n + lg d)τ d n ) = O(d n+1 + n 2 d n + nτ d n ) and so M -1 1 ≤ n n H(M 1 ) ≤ 2 η2 ≤ 2 O(d n+1 +n 2 d n +nτ d n ) . Combining the bounds for M -1 1
and M 2 we obtain the following bound for χ 1 which also a bound for the condition number of a complex root of the system.

χ 1 ≤ 2 η2 ≤ 2 O(d n+1 +n 2 d n lg d+(n+lg d)τ d n ) . (10)
The previous discussion leads to the following theorem Theorem 1. Let f = (f 1 , . . . , f n ) ∈ H be a 0-dimensional polynomial system such that its zero set consists of smooth points. Assume f i ∈ Z[X 0 , X 1 , . . . , X n ] such that they have degrees bounded by d and H(f i ) ≤ 2 τ . Then, we have the following bound for the condition number of any root ζ of the system

µ(f , ζ) ≤ 2 O(d n+1 +n 2 d n lg d+(n+lg d)τ d n ) .

Multivariate aggregate condition number

In this section we sketch the proof of an aggregate version of Theorem 1. It provides bounds similar to the ones of Proposition 2 and to the aggregate nature of the DMM bounds [6, Theorem 3].

In the view of Theorem 1 if we wanted to consider a bound on the condition number for all the roots of the system, then we have to multiply µ(f , ζ) by their number. There are d n roots in the worst case, by the Bézout bound. This leads to a bound of O B (d 2n+1 + d 2n τ ).

In the sequel we will improve this bound to O B (d n+1 +d n τ ) using aggregation. Some elementary properties are in place. We have to bound each factor independently. We sketch the approach for the second one. For the first factor we work similarly.

M ≤ M F ≤ n 2 H(M ) 2 ≤ n H(M ).
To bound ζ H(M 2 (ζ)) we can apply directly Eq. ( 5) or [START_REF] Hansen | Winning concurrent reachability games requires doubly-exponential patience[END_REF]. However, this approach gives an exponent of d 2n+1 , which is a big overestimation; by a factor of d n .

We rely on aggregation bounds of polynomial system, provided by the DMM bounds [START_REF] Emiris | The DMM bound: Multivariate (aggregate) separation bounds[END_REF]. Consider the polynomial f n+1 (X, Y ) = Y -X 2 1 -• • • -X 2 n and the polynomial system

(Σ i,j ) {f 1 (X) = • • • f n (X) = f n+1 (X, Y ) = 0}. ( 11
)
The resultant of the system encapsulates (all) the evaluations of f n+1 over the roots of f . Therefore, it suffices to bound the height of the resultant. The bounds that we get are similar to the ones of the previous section. The calculations lead to the following theorem Theorem 2. Let f = (f 1 , . . . , f n ) ∈ H be a 0-dimensional polynomial system. Assume f i ∈ Z[X 0 , X 1 , . . . , X n ] such that they have degrees bounded by d and H(f i ) ≤ 2 τ . Then, if ζ runs over all the solutions of the system, it holds

χ1 (f ) = ζ χ 1 (ζ) ≤ 2 O(d n+1 +d n τ ) .

  If the entries of the matrix M depend on a root ζ then we write M (ζ) to emphasize this. In this context it holdsχ 1 (ζ) ≤ M -1 1 (ζ) M 2 (ζ) ≤ (n + 1) 2 H(M 1 (ζ)) n+1 H(M 2 (

Acknowledgments

ET is partially supported by GeoLMI (ANR 2011 BS03 011 06), HPAC (ANR ANR-11-BS02-013), and an FP7 Marie Curie Career Integration Grant.


Patrick Kaplanian

BODILY, SPACIAL AND SOCIAL HIERARCHY IN LADAKH 1

The Ladakh districts are peopled by somewhat more than 200,0002 inhabitants. This region, which covers 97,000 sq km, is located to the northeast of Kashmir, along the Sino-Indian border. It is still called "Indian Tibet"3 a name which has the advantage of pointing out its dual attachment: to Tibet, in cultural and religious matters, and to the Indian Federation, in political matters. The Ladakhis are of Tibetan race and language. 55% of them practice Lama Buddhism. The Buddhists are concentrated in the valley of the Zanskar and the Indus. This study concentrates primarily upon the Indus valley. This area is located behind the great Himalayan chain, and being thus sheltered from the effects of the monsoons presents an arid, death-like aspect. The high altitude, an average of 3,500 m for the Indus valley, and the distance from the ocean explain the striking temperature ranges which occur not only seasonally but daily. Villages are virtually oases where the fields are irrigated solely by melting snows. In general, the villages are rather scattered, as we shall see further on.

Before referring to the villages, we shall consider the houses. They consist of either 1, 2 or 3 floors, depending upon the family's wealth. Two is the most common figures a ground floor and an upper floor. The lower level would usually be occupied by the animals, whereas the people would live on the upper level. If there are two upper floors the first is used in winter, and the second in summer. 4 The most important room in the house is the kitchen, which is the habitual meeting place. Meals are taken here, and the most talkative individuals gather to converse and drink chang (fermented barley) or salted tea with butter. The room is arranged around the hearth (thap; spelling thab) which is made of metal or earth and is placed against one of the walls, which is equipped with shelving covered with cooking-ware. The other walls are generally bare. Adjacent to the kitchen, and usually only accessible through it, is the dzot (spelling mdzod), the pantry or larder. In many houses there is a Ihubang (spelling klu-bang 5 , in Tib. klu-khang) in the dzot, which is consecrated to the lhu, underground divinities (spelling klu) who are providers of wealth and abundance. Every floor is equipped with a latrine: a small, door-less room 6 with a hole in the floor. One relieves oneself on the earth-covered floor (or directly into the hole). Excrement is then sent down the hole with a hit of earth so that it accumulates at the ground level, thus enriching the supply of natural fertilizer. 7 Scoops are provided for this purpose. Most of the other rooms are multi-functional. In certain houses there are specialized rooms such as shingkhang, rooms for storing wood (shing); changkhang, rooms for storing chang in large earthen jars; silo rooms (pang-a; spelling banga 8 ). But there is no equivalent to our bedrooms, or even the idea of given members of the family (parents, grand-parents, children) having rooms of their own. Particular mention should be made of the chotkhang (spelling mchod-khang), the private 'chapel' of the house, Every house has one. The far wall is covered with painted wooden recesses destined to hold statues of divinities. There is a striking contrast between the rich decoration of these recesses, as well as the scrolls of religious paintings (thangka; spelling thang-ka) which are hung on the walls on either side of these niches, and the simplicity of the other rooms. The chotkhang is decorated with sacred books, and with stucco, wood, or bronze images. Monks gather there to pray for the members of the household. At the top of the house is a flat terrace surrounded by a small parapet. This may be considered an additional room; one without a roof and one in which many activities take place. In winter, it is a favorite meeting place in the middle of the day, for soaking in such pale rays of sunlight as there may be. In the summer, many small tasks are carried out on the roof: cheese is dried, barley is roasted, wool is combed, etc. The terrace serves also as a storage place for wood, used for heating as well as for dzo9 (mdzo) dung, which is another fuel. Unless the astrologer (onpo; spelling dbon-po) decrees otherwise, the main entrance to the building faces east. The Ladakhis consider the east, and in conjunction, the south, as good directions. They sleep, for example, with their heads towards the east. However, when there is a monastery nearby, a chotkhang on the floor where they are sleeping, it is towards this that they turn in order to sleep. To paraphrase Bourdieu, one might say that the chotkhang is the east of the floor of the house on which it is located.10 Religion or religious imagery, thus creates a barrier against the ill effects of evil directions. Furthermore, when one is in a closed room located on a floor where there is no chotkhang, it is less serious to violate the rule of sleeping facing the east than it would be out of doors or on the terrace. A wall will thus counteract the ill effects of an evil direction, but will not have the same radical effect as a religious object (monastery, chotkhang, image). Most important, a wall will not in any way modify a privileged direction. We can state, therefore, that cultural space can be defined by a degree of distance in relation to natural, cosmographical space, even though the two are in harmony, since the house as a whole seen from outside is perfectly oriented on this same east-west axis. Religious space, on the other hand, delineates a complete break with cosmogeographical space, as the chotkhang may be oriented in any direction, and for those on the same level in the house, the chotkhang becomes the new focal point. Similarly, monasteries do not necessarily face east; in fact, most face south. In any case, religious constructions aside, we have these homologuesfront : rear of the house :: east : west :: head : foot (read: the front of the house is to the rear of the house as the east to the west and as the head to the feet)which initially define an isomorphism between cosmogeographical space, the dwelling, and the body. The demonstration of this isomorphism could easily be continued. For example, the front/rear opposition couples with the east/west opposition. Morning and evening the Ladakhis must kneel, facing the direction towards which they will sleep (or have slept). This front/back opposition is expressed in a series of very strict rules of etiquette: it is forbidden to turn one's back to a person, a religious image, to the kitchen hearth; women are obliged to wear a lokpa (slog-pa) on their backs (a goatskin which is at times replaced with brocade, or even a shawl). maintained when he is standing and becomes homologous not in terms of east and west, but in terms of high and low. This is also manifested in the rules of etiquette which are equally strict as those concerning the front/back opposition: it is forbidden to point one's foot towards a religious image, a person, the kitchen hearth, food, etc. A ladakhi proverb states that "even a mon 12 would not be able to tolerate a king pointing his foot at him". The only sitting position allowed is crosslegged. When one is moving through a room in which people are sleeping, one must avoid walking too close to them. It would be far more serious to pass over their heads than over their feet. In getting up, one must also avoid passing over any vessel containing food placed in front of one.

The Ladakhis themselves give a simple explanation for this: the feet are dirty; one is always walking in the dirt, in particular in the toilets, because of the climate, one does not take one's shoes off when entering the house, or even the kitchen. Of course, this is not a very satisfactory explanation. Taking off one's shoes and washing one's feet would change nothing. However, this explanation does show the opposition which corresponds to dirty/clean (most often, only the face is washed) or even impure/pure. The opposition is so strong that it takes precedence even over that of east and west. For example, if a group of persons has to sleep in a tent having dimensions such that all may not lie in a row side by side and face east, but must lie in two rows (see figure 2-a), then they sleep head to head (figure 2-b) or, at worst, feet to feet (figure 2-c), which implies that not all of them will be turned to the east.

The opposition between head and feet is maintained whether the body is in a vertical position or a horizontal one. This allows for mediation between the horizontal axis (front : rear of the house :: front : back :: east : west) and the vertical axis. There is another element which allows for this mediation: the sago-namgo. At times the onpo ordain that the head of a goat (namgo) or dog (sago) be placed in order to close the doors (go, spelling. sgo) of the sky (nam, spelling gnam) or the earth (sa) against demons coming from these two directions. In general the namgo is located near the main door, turned towards the east, while the sago is placed on the other side of the house facing west. 13 The list of homologues has thus become: front : rear :: front : back :: east : west :: head : feet :: sky : earth. The general framework of these spatial homologues having been defined, we shall concentrate on the vertical axis. We have seen that it is the most important, since in the case of conflict, the head/feet opposition takes precedence over that between east and west. It is upon this that the hierarchies are based: i.e. the social hierarchy, the hierarchy between the pure and impure, between the sacred and the profane. How is this materialized? First of all, within the framework of the house, the ground floor is always the animals , habitat. Agricultural tools, linked to the earth, and in particular, natural fertilizers of animal and human origin are stored there. This usage of the ground floor as a stable can be very well explained for practical reasons. However, the opposition between high and low becomes immediately apparent when one notes that the chotkhang is always on the upper floor; on the first floor if there is only one, and on the second if there are two above ground level. Certain houses which have but one floor still place the chotkhang on the terrace. The chotkhang and the ground floor are two extremes: on the one hand that which is religious, pure, of the sky, the residence of the gods; on the other, that which is dirty, impure, the earth. These two poles are reflected by the social hierarchy. When the king of Ladakh is invited into a house, he does not enter by the door; a ladder is placed against the wall so that he immediately steps onto the terrace. Those questioned explain that he should not be obliged to go through the ground floor, which is dirty, full of mud, and animal excrement. In fact, the king places himself directly at the level which corresponds to his social rank, i.e. at the highest point in the house. Although it is not the royal family's habit to visit subjects, the current queen's father-in-law did so. 14 It is interesting to note that the lhatho (lha-tho) of the pha(z)lha (pha-lha) 15 protector of the phaspun (pha-spun) is most often located on the roof of the chotkhang. The better instructed persons questioned affirmed the superiority of orthodox Lamaism over the popular religion. 16 And the monks insist that if they are to tolerate the lhatho they are against its being placed inside the chotkhang. Paradoxically, their attitude leads their followers to place popular religion above Lamaism.17

Eating habits give us a second lead. First of all, one must never place one's cup on the ground. In the kitchen, in front of the cushions upon which one sits cross legged, long, low tables are provided on which to place bowls and cups. Outdoors, one would utilize any object rather than a stone. A brick, for example, would be preferable 'because it is a man-made object. The object holding the cup serves not only to put it in a spatial, hierarchic position in relation to the ground, 14 I remind that this paper was written in 1975-1977. 15 The word phaspun. indicates a group of families or houses. Its function is only apparent upon three occasions: birth, marriage and death. This function is at the same time practical, (for example, the members of a phaspun join forces to gather wood for a cremation); ritualistic, (other examples: the members of a phaspun accompany the bride to her husband's house; they move about the funeral pyre, carrying a special scarf, etc.); and religious (a certain number of taboos: the body of a dead person may only be touched by the members of his phaspun; at the time of birth only the members of the family's phaspun may accept food from them during 7, 15 or 30 days, as the case may be, etc.). In the Indus valley one may change phaspun. In the Zanskar valley, the phaspun are exogamous and one cannot change. Paradoxically, however, in the case of a "son-in-law" marriage (makpa, spelling mag-pa, a young man marries the daughter of a family in which all the children are girls and agrees to live with his parents-in-law, although marriage is normally patrilocal), the son in law in question is taken into the same phaspun as his new wife, or at worst, into the phaspun of another village which has the same pha(z)lha. The pha(z)lha is the phaspun's guardian deity. It lives in a lhatho (lha: divinity). A lhatho is a structure which is more or less cubical, and crowned with poplar or shukpa branches (shug-pa; Juniperus wallichiana: the pencil cedar). These are decorated with ceremonial scarves which are called khataks (bkha-tags. most often pronounced kata or katha in Lhasa) and placed in a vertical position on top of the cube. In the case of the pha(z)lha 's lhatho the branches are changed at the beginning of each new year. Branches from the shukpa are used, and it is the male members of the phaspun who change them. There are also lhatho for the guardian deities of the village (yullha. yul: village), of the monastery (gonlha, from gonpo; spelling: mgon-po: protector or dgon-lha from dgon-pa, monastery), and the royal palace (tselha). Most often, though not always, they are placed in a high position. 16 Apart from the many divinities of Lamaism, about which most of the laity and even many monks know very little, the Ladakhi believe in a myriad of local deities which are linked to various elements of the landscape (rocks, rivers, etc.). I have already mentioned the lhu, underground and/or aquatic deities linked with wealth, as well as the local benevolent deities. To this list, we must add the tsan (btsan), ambiguous beings which may be both evil and benevolent. They are linked to the wilderness, but live in inhabited areas. They are characterized by two things: their red color, and their lack of a back (from behind, their heart and lungs can be seen). This absence of a back can no doubt be linked to prohibitions concerning the back, and the womens' obligation to wear a lokpa (slog-pa), a goatskin or sheepskin which is attached to the shoulders and falls to the waist. but t o separate cooked food and culture from the earth itself, from nature, by means of an object which in itself is of the realm of culture. There are also attitudes of respect as regards food, when one is offered tea or soup, one must hold the cup or bowl below the vessel which the woman who is serving holds, or quite simply, leave the empty glass on the table without holding it. 18 If one takes the initiative of getting up in order to be served at the hearth, one must similarly hold the cup at the foot of the hearth, but without placing it on the ground. That which is true for food is also true for knowledge (which is always more or less connected to religion). One never places a book on the ground. One never sits on it. And it is better to place it on the table than on one's knees. Everyone holds the same attitudes towards food and knowledge. However, the social and religious hierarchy manifests itself in another way in the case of food: in the arrangement of individuals in the room, and in the height of the tables placed before them. The starting point is the hearth, which is placed against one of the four walls of the kitchen. On one side (either left or right) is the woman who is cooking. On the other side, the eldest male is generally seated, most often, the father-in-law (since it is a patrilocal society). It is he who removes embers from the fire as the need arises, and puts them into a receptacle placed there for this purpose. His seat is the most important in the hierarchy, as we shall see. It is also the "good place" where one can warm one's hand.

Figure 3 -Arrangement of guests in a kitchen. H: hearth, W: woman cooking, 1,2,3 hierarchic order, 1 being the grandfather's seat, s: screen pulled out in order to separate the cook from the lower strata.

If a gathering is organized, the guests will seat themselves according to hierarchic order. The first in this order places himself in the grand-father's seat (figure 3) The order is illustrated above. 19 1 rinpoche 2 lamas (monks) 3 kalhon, lhonpo 4 ordinary people (elders before youngest) 5 gara, mon, beda. This structured order is not in itself sufficient. To reinforce it, tables of varying heights are used. For example, in front of the rinpoche, one places a very high table, considered as a throne 20 . In front of the lamas (bla-ma), the kalhon (bka'-blon), and the lhonpo (blon-po) , a high table is placed on top of an ordinary table; in front of the people of average strata, one places an ordinary Ladakhi. The goba (mgo-ba) is the village chief, and is elected. The garas (sp. mgar-ba) are still a stratum of ironsmiths; the mons of musicians and carpenters; the bedas of bards. It is noted that this arrangement puts priority on religion. It does not correspond, in fact, to the division of Ladakhi society into three strata, where the religious and the secular are mixed; 1 king, kalhon, lhonpo 2 "ordinary people" (peasants) and plain lamas, 3 garas, mons and bedas. According to the information from the village of Matho, reported by P. Farrington and N. Grist, the garas are placed above the mons in the hierarchy, since on the arrow, the iron tip made by the former is in front of the wooden shaft made by the latter. 20 As far as the rinpoche (very high reincarnated lama) is concerned I am just repeating here what most informants told me in the 1970s. However five years later I had the opportunity to attend a very important wedding where the rinpoche of Rizong was present . He was not on the highest pillow in front of the highest table but given a seat in a room separated from the other guests. It was confirmed to me afterwards that, actually a rinpoche is not seated at the place of honor at the head of a row but locked in a separate room. On the other hand in monasteries the rinpoche has his own throne and often a second throne, even higher, is reserved for the highest rinpoche of the school in question (the Dalai Lama for example). His photo is put on the seat.

table; before the mon and gara a board, and before the beda , nothing at all, or possibly a board (Figure 4). 21 A choktse22 ; courtesy Céline Moulys

The case of the bedas is of particular interest. In theory, they are characterized as "not having a house"; these wandering bards are the limit of humanity, of culture. They are barely tolerated inside the kitchen, and are sometimes excluded and have to eat outside. They merely have a board on which to place their cups, sometimes nothing, and have to place it on the ground. They have an ambiguous position. They remain part of the social structure when they are at the far end of the kitchen, and have a board to use. They are no longer a part of it when they are forced outdoors, and must put their bowls on the ground. House, kitchen; there is yet one last area in which space reflects the hierarchy: urbanism. It is manifested at the level of the village by the predominant positions of the royal palace and the monastery. For the most part, the monastery is on a higher elevation than the palace. Although other criteria are often given by those questioned in order to justify this position, such as the need for defense measures in past times, the superiority of the king over his subjects, and of the sacred over the unholy is also a theme frequently heard. 23 It is true that when confronted with the current urban situation, we cannot go beyond this statement. It would, however, be perfectly consistent with previously given data to visualize an urban area hierarchically organized in concentric circles: a projection of the social pyramid. In fact, according to the Ladakhis themselves, when the village was gathered at the top of the hill, and protected by walls, 24 this was indeed toe case. The houses of the kalhon, the lhonpo, and the nobility were near the palace, whereas those of the lower strata were further away. Archaeological findings will verify these comments, which in any case are a reflection of mental structures. But evolvement towards the breaking up of groups of compact dwellings is continuously in process. 25 Unfortunately, these are small hamlets, which do not have a royal palace. Dwellings in large villages have already been completely dispersed. However, in villages of secondary size, one notices that there are a few, isolated houses of recent construction. The inhabitants explain that certain families had their homes reconstructed "in order to be closer to the fields". But why have they waited until now to do so? This second question generally remains unanswered. Although inhabited space is indeed the reflection of a highly hierarchic society, this society is evolving, after having remained immobile for a long time. Although the kings, kalhon and lhonpo and other important groups have maintained their prerogatives up to this timein spite of the abolition of the monarchy by the Dogra more than a hundred years agotraditional urbanism now continues to exist only through remainders. The last of the royal palaces, in which the queen currently lives, is in Stok. It was constructed during the 19th century, and is located at the bottom of the valley, at a lower elevation than the village. Thus, Ladakhi society is strictly hierarchic. The oppositions between the sacred and the unholy, between the religious and the secular, between pure and impure, between gods and men, between the different strata of society, between culture (cooked food) and nature (earth, animals) are expressed through positions in space which are graduated from high to low. They are projected on the house, the human body, the village, cosmic space, and even geographical space. 26 Titles of nobility still hold their prerogatives in protocol. But the destructuring of the urban network has marked an evolution. If it no longer reflects the social hierarchy as it once did, it is because this is losing relevance. There is a good possibility that the social attitudes that reflect this social hierarchy will also follow the same path. Attitudes of revolt can be seen today. A number of young people who have learned English and Urdu in school and afterwards found state-supported positions in Leh, the principal urban complex, refuse for example, to sit in the places assigned to them when they come home. Nonetheless, it is remarkable, after more than 130 years under the Dogra, English, and then Kashmiri colonialism, that attitudes have remained unchanged, as if the monarchy and the entire complicated apparatus of the nobility were still the status quo. After all, didn't the Ladakhi elect their queen to a seat in Parliament in New Delhi in the summer of 1977? Today, it is still widely said that in such and such a village the archery festivals are very lovely, "because that is a village where all the inhabitants serve the palace". In fact it can be nothing of the sort. The queen has but a few servants 27 .

Translated from French by Maria Phylactou (London school of Economics). Drawing by Lucy Vallauri (CNRS, Aix en Provence) Patrick Kaplanian 25 Since the writing of the first version of this article this movement has been accelerated. The housing environment is increasingly scattered. This dispersal is strengthened by the increase of secondary houses subsequent to the division of the estate between brothers, which is a recent phenomenon. 26 Karl Marx, 3 documents relating to the history of Ladakh, Journal of the Asiatic Society of Bengal, 1891, Vol. LX, p.117, n.27: "To Ladakh people 'going in the direction of Lhasa' is 'going up', 'coming away from there' is equal to 'going down'" 27 I have used the following symbols in the order of the Tibetan alphabet.

Figure 1 -

 1 Figure 1 -Very simplified plan of a Ladakhi house 1. Stables, sheepfold -2. Latrines -3. Kitchen, a. hearth -4. Dzot, a. lhubang -5. Chotkhang, a. setting for the statue of the main divinity -6.Parapet on the terrace -7. Tarcok (dar-lcog) -8. Lhato -9. Tsandos (btsan-mdos, red painted stone to keep the tsan, btsan away) -10. Sangsphor or sangspor (bowl for the morning fumigations of shukpa; shug-pa) -11. Low wall of the garden -12. Sangskhung 11 for the fumigations of shukpa in case of the visit of a rinpoche.

  Rebecca Norman for her help to find out the proper orthographies, and some comments and advise.

	ka	kha	ga	nga
	ca	cha	ja	ña
	ta	tha	da	na
	pa	pha	ba	ma
	tsa	tsha	dza	wa
	zha	za	'a	ya
	ra	la	sha	sa
	ha	a
	I am thanking

This enquiry was carried out entirely through direct observation and interviews with Ladakhis, during 10 months in the field, broken up into the three summers of1975, 1976 and 1977. The conclusions partially concur with those described in an article by R. A. Stein, "L'Habitat, le Monde, et le Corps Humain en Extrême Orient et Haute Asie", Journal Asiatique, Volume CCXLVT/l, pp 37-74, to which I refer. This article is completed by another by the same author: "Architecture et Pensée Religieuse en Extrême Orient", Arts Asiatiques, Vol. IV, No. 3.

100 000 at the time of writing this article. I will mention other changes since 1975.

See for instance the title of the book Antiquities of Indian Tibet by A. H. Francke (Re-publication New Delhi, 1972).

In Globus. Vol. 73, page 4, A. H. Francke mentions a house with the kitchen on the ground floor.

Lhubang: "pantry or larder for the lhu". Tibetans prefer to write klu-khang "house for the lhu"

The absence of a door implies the lack of taboo surrounding the fact of seeing someone defecate. Occasionally there are two holes in the latrines.

Dog excrements alone are not used for any purpose.

Goldstein's New Tibetan English Dictionary: "bang-ba, storage cubicle for grain in a storehouse". It is the same bang as in lhubang, see note 5.

The dzo (mdzo) is a hybrid of the yak and the cow.

P. Bourdieu, Esquisse d'une Théorie de la Pratique, Geneva 1972. Title of chapter: "La Maison et le Monde renversé". In order that a comparison with Bourdieu's conclusions be of interest, one would have to demonstrate that the four cardinal points are redistributed indoors from the "new east", as he does with the case of the Kabyle house.

S.C. Das A Tibetan-English dictionary[1902] 1985, p. 1316 bsangs "incense, frankincense"; in Ladakhi sangs is the action of burning, not what is burned; p. 147 khung : "hole, pit, hollow, cavity". In Ladakh seems to mean before all the arrangement of 3 stones made to protect the fire from the wind.

Inferior stratum of musicians and carpenters.

Those questioned also speak of a camel's head as the sago, and the head of a hare or rabbit as the namgo. I have never had the occasion to verify this.

There are apparently cases in which the lhatho is in the chotkhang . I have never verified this for myself. At times, the pha(z)lha is at the same height as the chotkhang, in a special room. The most widely known example is that of the house of the kalhon of Leh, in Chanspa (see note 19). There the guardian deity, a gyapo (rgyal-po, the word simply means king) which is a divinity linked to the 5 directions, is represented by a mask which is locked up in a special room. This room is only opened once a year, on the occasion of the New Year.

This is in fact, a rather obvious practice, but the rule is explicitly laid down.

A rinpoche is a great, reincarnated lama. Lama (sp. blama) simply means monk. The kalhon or kalon (sp. bka'blon used to be the prime minister. This title was hereditary, and he still keeps it. This is also true for the lhonpo (governor). The kalhon or kalon is still a house name, while lhonpo is used to translate "minister" in modern

See R.A.Stein's article (ibid.) p. 73, n.61 : "Au Tibet, la hiérarchie des hauteurs s'exprime volontiers aussi par le nombre de coussins entassés qui servent de siège. Dans une hagiographie de Padmasambhava celui-ci occupe un siège formé de neuf coussins, l'abbé, un siège formé de cinq coussins et les traducteurs de tapis. Cette hiérarchie des hauteurs se double de celle horizontale, en droite et gauche. "

Sp. lcog-rtse or cog-rtse. This word is borrowed from Chinese and has no proper spelling. The Bod-rgya-tshig-Mdzod-chen-po gives 3 or 4 spellings included . lcog-rtse and cog-rtse

 23 It is not impossible that the height of domiciles also be a criterion. See R.A.Stein (ibid) p. 73, n.61: "La hiérarchie des étages s'est maintenue au Tibet et est attestée en Chine...... Le 'temple rouge' (mchod-khang dmar-po) construit sur le palais du Potala à Lhassa est dit avoir neuf étages, et le Dalai Lama est assis sur neuf coussins. Des bâtiments réels de neuf étages sont attestés au Tibet, à Tashi Lunpo et à Leh (le château). " Leh was the last royal capital of

Ladakh.24 It may still be verified that the houses were concentrated on top of a hill around the royal palace by visiting the ruins of Temisgam and Zangla (in the Zanskar valley).