Les automates cellulaires forment une famille bien connue de modèles dynamiques discrets, introduits par S.Ulam et J. von Neumann dans les années 40. Ils ont été étudiés avec succès sous différents points de vue: modélisation, dynamique, ou encore complexité algorithmique. Dans ce travail, nous adoptons ce dernier point de vue pour étudier la famille des automates cellulaires coagulants, ceux dont l’état d’une cellule nepeut évoluer qu’en suivant une relation d’ordre prédéfinie sur l’ensemble de ses états. Nous étudions la complexité algorithmique de ces automates cellulaires de deux points de vue : la capacité de certains automates coagulants à simuler tous les autres automates cellulaires coagulants, appelée universalité intrinsèque, et la complexité temporelle de prédiction de l’évolution d’une cellule à partir d’une configuration finie, appelée complexité de prédiction. Nous montrons que malgré les sévères restrictions apportées par l’ordre sur les états,les automates cellulaires coagulants peuvent toujours exhiber des comportements de grande complexité.D’une part, nous démontrons qu’en dimension deux et supérieure il existe un automate cellulaire coagulants intrinsèquement universel pour les automates cellulaires coagulants en codant leurs états par des blocs de cellules ; cet automate cellulaire effectue au plus deux changements d’états par cellule. Ce résultat est minimal en dimension deux et peut être amélioré en passant à au plus un changement en dimensions supérieures.D’autre part, nous étudions la complexité algorithmique du problème de prédiction pour la famille des automates cellulaires totalistiques à deux états et voisinage de von Neumann en dimension deux. Dans cette famille de 32 automates, nous exhibons deux automates de complexité maximale dans le cas d’une mise à jour synchrone des cellules et nous montrons que dans le cas asynchrone cette complexité n’est atteinte qu’à partir de la dimension trois. Pour presque tous les autres automates de cette famille, nous montrons que leur complexité de prédiction est plus faible (sous l’hypothèse P 6≠NP). / Cellular automata are a well know family of discrete dynamic systems, defined by S. Ulam and J. von Neumannin the 40s. The have been successfully studied from the point of view of modeling, dynamics and computational complexity. In this work, we adopt this last point of view to study the family of freezing cellular automata, those where the state of a cell can only evolve following an order relation on the set of states. We study the complexity of these cellular automata from two points of view, the ability of some freezing cellular automata to simulate every other freezing cellular automata, called intrinsic universality, and the time complexity to predict the evolution of a cell starting from a given finite configuration, called prediction complexity. We show that despite the severe restriction of the ordering of states, freezing cellular automata can still exhibit highly complex behaviors.On the one hand, we show that in two or more dimensions there exists an intrinsically universal freezing cellular automaton, able to simulate any other freezing cellular automaton by encoding its states into blocks of cells, where each cell can change at most twice. This result is minimal in dimension two and can be even simplified to one change per cell in higher dimensions.On the other hand, we extensively study the computational complexity of the prediction problem for totalistic freezing cellular automata with two states and von Neumann neighborhood in dimension two. In this family of 32 cellular automata, we find two automata with the maximum complexity for classical synchronous cellular automata, while in the case of asynchronous evolution, the maximum complexity can only be achived in dimension three. For most of the other automata of this family, we show that they have a lower complexity (assuming P 6≠NP).

Contexte : Malgré une volonté affichée traduite dans des textes et procédures, l’évaluation en France n’est que peu intégrée dans le processus de décision. Pourtant, dans le secteur de la santé confronté à de multiples défis, l’évaluation pourrait être une approche utile à la détermination des choix. L’utilisation de l’évaluation dépend d’une pluralité de facteurs, dont les connaissances produites et leur mode de production, les caractéristiques des décideurs et autres utilisateurs et le contexte sociopolitique et institutionnel de l’évaluation. Objectifs : Les objectifs de ce travail sont d’apprécier l’utilisation de l’évaluation dans les politiques de santé, d’identifier les leviers associés à cette utilisation et d’apprécier la capacité de l’évaluation à satisfaire les attentes et favoriser l’utilisation de ses productions. Méthode : Une revue de littérature a permis d’enrichir la compréhension du concept d’utilisation, d’identifier les facteurs influents et de faire émerger les problématiques associées. Considérant l’évaluation comme un système d’action complexe, un modèle basé sur une approche systémique a été construit et mis à l’épreuve à travers quatre étapes d’analyse des évaluations des plans régionaux de santé publique (PRSP) : (1) analyse globale de 16 évaluations ; (2) lien processus/utilisation dans une région ; (3) résultats à court/moyen terme dans 9 régions ; (4) études de cas approfondies et analyse multicritères dans 5 régions. Résultats : Une première analyse a éclairé les enjeux du contexte et la contribution des PRSP à la cohérence des politiques régionales de santé. L’examen du processus d’évaluation dans une région a montré la relation entre finalités, démarche et utilisations de l’évaluation. L’observation des suites de l’évaluation dans neuf régions a identifié différentes formes d’utilisation et les principaux facteurs intervenant. La dynamique de changement a été appréhendée dans la globalité des interactions entre le contexte, les acteurs et l’évaluation dans cinq régions. Discussion : Les retombées de l’évaluation sont plus à chercher du côté des savoirs accumulés et des évolutions des pratiques que dans des décisions formelles transformant de façon radicale les politiques. Le contexte, la crédibilité de l’évaluation, l’engagement et la motivation des acteurs sont des facteurs déterminants. Des pistes de recherche sont envisagées en vue d’approfondir les conditions du développement des capacités et de la culture d’évaluation, elles-mêmes indispensables à une meilleure exploitation de l’évaluation / Context: Despite the willingness showed in texts and procedures, evaluation in France is little integrated in the decision making process. However, in the health sector which faces multiple challenges, evaluation should be a useful approach to select choices. The use of evaluation depends on multiple factors such as, knowledge and its production process, characteristics of decision makers and others users, and the political and institutional context of the evaluation Objective: The objectives were: to assess the use of evaluation on health policies; to identify levers associated with use; to assess the capacity of evaluation to fit with decision-makers needs and to enhance usability. Method: Literature review allowed to enrich the understanding of the concept of use and to identify the main influent factors as well as the related issues. Regarding evaluation as a complex system, a model based on a systemic approach was built and tested in evaluations of regional public health plans (PRSP) in 4 steps: (1) global analysis of 16 evaluations; (2) relation process/use in on region; (3) use at short/medium term in 9 regions; (4) case studies and multicriteria analysis in 5 regions. Results: A first analysis enlighted the context and the contribution of the PRSP to the coherence of regional policies. A deeper process analysis carried out in one region pointed out the relation between final aims, management and evaluation use. The examination of evaluation consequences conducted in nine regions identified different forms of use and the major factors associated with them. The dynamic of change has been apprehended as a whole through the interactions between context, users and evaluation in five regions. Discussion: The effects of evaluation are more obvious in terms of knowledge building and evolution of practice than in radical change of policies. Context, evaluation credibility, actors’ commitment and motivation are key factors. Future research should help to better understand how to foster the culture and the capacities of evaluation. These are important prerequisites to a wider use of evaluation

Contexte – Les interventions de santé publique et plus particulièrement les interventions de promotion de la santé sont considérées comme « complexes ». Leur évaluation représente un défi tant pour les chercheurs – lorsqu’il s’agit de caractériser ce qui produit des effets – que pour les acteurs – lorsqu’il s’agit de transférer une intervention d’efficacité prouvée –, notamment en raison de la forte influence du contexte sur l’efficacité de ces interventions. Cette problématique de la complexité soulève plusieurs questions aussi bien conceptuelles qu’opérationnelles : comment les chercheurs et acteurs appréhendent-ils ces notions en vue de développer, d’implanter, de « routiniser », ou de transférer une intervention ? Quels sont alors les méthodes et les outils évaluatifs qui permettraient de mieux appréhender la complexité de ces interventions ? Objectifs – L’objectif général de cette recherche doctorale est d’explorer l’appréhension et l’utilisation de la complexité par les chercheurs et les acteurs de terrain en santé publique et plus particulièrement en promotion de la santé. Plus spécifiquement, il avait pour objectifs de : décrire et analyser les dimensions de la complexité identifiées par les chercheurs et par les acteurs de terrain, en particulier les éléments constitutifs des interventions et de leurs contextes d’implantation ; décrire et analyser comment les chercheurs et acteurs s’appropriation les concepts de la complexité et prennent en compte la complexité des interventions dans le développement, la mise en œuvre, l’évaluation et le transfert des interventions. Méthodes – Pour répondre à ces objectifs, nous avons procédé en deux étapes. La première consistait en une revue mixte de la littérature et visait notamment à identifier l’appréhension de la complexité faite par les chercheurs l’influence de celle-ci sur leurs choix méthodologiques. La seconde a été réalisée à partir d’une étude de cas afin : de proposer une description fine de la complexité du terrain à la fois par les acteurs et avec notre regard de chercheur forméà la complexité ; d’identifier la manière dont les acteurs prenaient en compte la complexité dans leurs pratiques. Résultats – Les résultats croisés de la revue de la littérature et de l’étude de cas identifient deux dimensions majeures de complexité : les caractéristiques des parties prenantes et le contexte. Si la notion de complexité est d’actualité en recherche, nos travaux montrent qu’elle reste difficile à justifier et à décrire. La complexité, fortement reconnue par les chercheurs, avait influencé la réalisation d’adaptations méthodologiques lors de l’élaboration et/ou de l’évaluation de leurs interventions notamment par l’application des recommandations du Medical Research Council. La prise en compte de la complexité par les acteurs se rencontre quant à elle essentiellement dans les adaptations qu’ils réalisent au quotidien. Discussion – Cette recherche doctorale soulève trois points de discussion et de perspectives : la définition de la complexité et ses évolutions attendues au regard de la mise en évidence de l’importance du dynamisme des interventions ; le reporting des interventions comme levier d’amélioration de développement et d’évaluation des interventions ; la plus-value des espaces partagés acteurs-chercheurs dans la production de données probantes / Context – Public health interventions and especially health promotion interventions are considered « complex ». Their evaluation represents a challenge for researchers, which aims to communicate a proven effectiveness intervention with strong contextual influence on the effectiveness of these interventions.This issue of complexity raises several conceptual as well as operational questions: how do researchers and actors understand these notions in order to develop, implement, « routine », or transfer an intervention? What are the evaluation methods and tools that would make it possible to better understand the complexity of these interventions? Objectives – The general objective of this doctoral research is to explore the apprehension and use of complexity by researchers and stakeholders in public health and more particularly in health promotion. More commonly, it aimed to: describe and analyze the dimensions of the complexity identified by researchers and stakeholders, particularly the components of interventions and their contexts; describe and analyze how researchers and stakeholders appropriate the concepts of complexity and take into account the complexity of interventions in the development, implementation, evaluation and transfer of interventions. Methods – To meet these objectives we proceeded in two stages. The first stage consisted of a mixed review of the literature and aimed particularly at identifying the apprehension of the complexity made by the researchers of the influence of thisone on their methodological choices. The second stage was realised from a case study: to propose a fine description of the complexity of the field both by the actors and the researcher trained to the complexity; to identify the way in which the actors took into account the complexity in their practice. Results – The crossed results of the review of the literature and the study of two major dimensions: the characteristics of the stakeholders and the context. If the notion of complexity is relevant in research, our work highlight that it’s still hard to justify and describe. Researcher responsiveness has been influenced by methodological adaptations in the development and / or evaluation of their interventions, including the implementation of the recommendations of the Medical Research Council. Consideration of the complexity by the actors meets in the adaptations which are imposed on a daily basis. Discussion – This doctoral study raises three points of discussion and perspectives: the definition of the complexity and its evolutions which intervene with regard to highlighting the importance of dynamic interventions; the reporting of interventions as a lever for improving the development and evaluation of interventions; the added value of shared spaces between actors and researchers in the production of evidence

Dans la première partie, on propose un système de type pour le lambda-calcul, dans le style du calcul des séquents, nomme « Soft Type Assignment » (STA) qui est inspiré par la logique linéaire « soft ». STA a la propriété de réduction du sujet et est correct et complète pour les calculs en temps polynomial. Par la suite on propose un déduction naturelle, STA_N. Ce système est simple mais il a le désavantage que les variables dans le sujet peuvent être explicitement renommées. Pour résoudre ce problème, on propose le système STA_M, où les contextes sont des multi-ensembles, donc les règles pour renommer les variables peuvent être interdit. L’inférence de type pour STA_M ne semble pas décidable. On propose un algorithme qui pour chaque lambda-terme rend l’ensemble de contraintes que doivent être satisfait pour que le terme soit type. Pi est correct et complet. Ensuite on étend le lambda-calcul par des constantes booléennes et on propose le système STA_B. La particularité de STA_B est que la règle du conditionnel utilise les contextes de façon additive. Chaque programme de STA_B peut être exécuté, par une machine abstraite, en espace polynomial. De plus le système est aussi complet pour PSPACE. Dans la deuxième partie, on propose une restriction de PCF, nommée SlPCF. Ce langage est équipé avec une sémantique opérationnelle qui mélange l’appelle par nom et l’appelle par valeur et peut être interprèté en mode standard dans les espaces cohérents linéaires. SlPCF est complet pour les fonctions récursives, mais il n’est pas complet et donc il n’est pas fully abstract pour les espaces cohérents linéaires / In the first part, we propose, inspired by Soft Linear Logic, a type assignment system for lambda-calculus in sequent calculus style, named Soft Type Assignment (STA). STA enjoys the subject reduction property. and is correct and complete for polynomial time computations. Then, we propose a natural deduction named STA_N. While simple, STA_N has the disadvantage of allowing the explicit renaming of variables in the subject. To overcome to this problem, we propose another natural deduction system, named STA_M, where contexts are multisets, hence rules renaming variables can be avoided. The type inference for STA_M seems in general undecidable. We propose an algorithm Pi returning, for every lambda-term, a set of constraints that need to be satisfied in order to type the term. Pi is correct and complete. We extend the lambda-calculus by basic boolean constants and we propose the system STA_B. The peculiarity of STA_B is that the conditional rule treats the contexts in an additive way. Every STA_B program can be executed, through an abstract machine, in polynomial space. Moreover, STA_B is also complete for PSPACE. In the second part we propose a restriction of PCF, named SlPCF. The language is naturally equipped with an operational semantics mixing call-by-name and call-by-value parameter passing and it can be interpreted in linear coherence space in a standard way. SlPCF is recursive complete, but it is not complete, and thus not fully abstract, with respect to linear coherence spaces

Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n}) / Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n})

Les dernières années ont témoigné une augmentation spectaculaire de la demande des communications sans-fil à taux élevé. Afin de répondre à ces nouvelles exigences, le recours aux techniques Multiple-Input Multiple-Output (MIMO) était inévitable, car ils sont capables d’assurer une transmission fiable des données à haut débit sans l’allocation de bande passante supplémentaire. Dans le cas où l’émetteur ne dispose pas d’information sur l’état du canal, les techniques de codage spatio-temporel se sont avérées d’exploiter efficacement les degrés de liberté du canal MIMO tout en profitant du gain de diversité maximal. D’autre part, généralement la complexité de décodage ML des codes espace-temps augmente de manière exponentielle avec le taux ce qui impose un défi important à leur incorporation dans les normes récentes de communications. Reconnaissant l’importance du critère de faible complexité dans la conception des codes espace-temps, nous nous concentrons dans cette thèse sur les codes espace-temps en bloc où la matrice du code peut être exprimée comme une combinaison linéaire des symboles réels transmis et nous proposons des nouveaux codes qui sont décodables avec une complexité inférieure à celle de leurs rivaux dans la littérature tout en fournissant des meilleurs performances ou des performances légèrement inférieures. / The last few years witnessed a dramatic increase in the demand on high-rate reliable wireless communications. In order to meet these new requirements, resorting to Multiple-Input Multiple-Output (MIMO) techniques was inevitable as they may offer high-rate reliable wireless communications without any additional bandwidth. In the case where the transmitter does not have any prior knowledge about the channel state information, space-time coding techniques have proved to efficiently exploit the MIMO channel degrees of freedom while taking advantage of the maximum diversity gain. On the other hand, the ML decoding complexity of Space-Time Codes (STCs) generally increases exponentially with the rate which imposes an important challenge to their incorporation in recent communications standards. Recognizing the importance of the low-complexity criterion in the STC design for practical considerations, this thesis focuses on the design of new low-complexity Space-Time Block Codes (STBCs) where the transmitted code matrix can be expressed as a weighted linear combination of information symbols and we propose new codes that are decoded with a lower complexity than that of their rivals in the literature while providing better or slightly lower performance.

Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.

MLF est un système de types combinant le polymorphisme implicite de seconde classe de ML avec le polymorphisme de première classe mais explicite du Système F. Nous proposons une représentation des types de MLF qui superpose un graphe acyclique orienté du premier ordre (encodant la structure du type avec partage) et un arbre inversé (encodant la structure de lieurs du type). Cela permet une définition simple et directe de l'instance sur les types, qui se décompose en une instance sur la structure du type, des opérations simples sur l'arbre de lieurs, et un contrôle acceptant ou rejetant ces opérations. En utilisant cette représentation, nous présentons un algorithme d'unification sur les types de MLF ayant une complexité linéaire.<br /><br />Nous étendons ensuite les types graphiques en un système de contraintes graphiques permettant l'inférence de types à la fois pour ML et MLF. Nous proposons quelques transformations préservant la sémantique de ces contraintes, et donnons une stratégie pour utiliser ces transformations afin de résoudre les contraintes de typage. Nous montrons que l'algorithme résultant a une complexité optimale pour l'inférence de types dans MLF, et que, comme pour ML, cette complexité est linéaire sous des hypothèses raisonnables.<br /><br />Enfin, nous présentons une version à la Church de MLF, appelée xMLF, dans laquelle tous les paramètres de fonctions, toutes les abstractions de type et toutes les instantiations de types sont explicites. Nous donnons des règles de réduction pour réduire les instantiations de types. Le système obtenu est confluent lorsque la réduction forte est autorisée, et vérifie la propriété de réduction du sujet. Nous montrons aussi le lemme de progression pour des stratégies faibles de réduction, dont l'appel par nom et l'appel par valeur en restreignant ou non le polymorphisme aux valeurs. Nous proposons un encodage de MLF dans xMLF qui préserve les types, ce qui assure la sureté de MLF.

.

Différentes analyses de la méthode de Givens en parallèle sur une architecture à mémoire partagée sont examinées. Présentation de résultats de complexité et d'algorithmes asymptotiquement optimaux. Dans une deuxième partie, consacrée aux architectures à mémoire distribuée, les couts de communication sont pris en compte. Une analyse macroscopique montre l'influence de l'architecture sur la complexité des décompositions de Givens et de Householder s'exécutant sur différents réseaux de processeurs fonctionnant par échange de messages