Orientador: Aurelio R. Leite Oliveira, Marta Ines Velazco / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T08:57:24Z (GMT). No. of bitstreams: 1 Silva_Jairda1_D.pdf: 1755258 bytes, checksum: 2ecb493aab3646838f54c2df2012b5d9 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho apresentamos uma nova família de algoritmos para resolver problemas de programação linear. A vantagem desta família de algoritmos é a sua simplicidade, a possibilidade de explorar a esparsidade dos dados do problema original e geralmente possuir raio de convergência inicial rápido. Esta família de algoritmos surgiu da generalização da idéia apresentada por João Gonçalves, Robert Storer e Jacek Gondzio, para desenvolver o algoritmo de ajustamento pelo par ótimo. Este algoritmo foi desenvolvido por sua vez tendo como base o algoritmo de Von Neumann. O algoritmo de Von Neumann possui propriedades interessantes, como simplicidade e convergência inicial rápida, porém, ele não é muito prático para resolver problemas lineares, visto que sua convergência é muito lenta. Do ponto de vista computacional, nossa proposta não é utilizar a família de algoritmos para resolver os problemas de programação linear até encontrar uma solução e sim explorar a sua simplicidade e seu raio de convergência inicial geralmente rápido e usá-la em conjunto com um método primal-dual de pontos interiores infactível, para melhorar a eficiência deste. Experimentos numéricos revelam que ao usar esta família de algoritmos em conjunto com um método primal-dual de pontos interiores infactível melhoramos o seu desempenho na solução de algumas classes de problemas de programação linear de grande porte. / Abstract: In this work, we present a new family of algorithms to solve linear programming problems. The advantage of this family of algorithms relies in its simplicity, the possibility of exploiting the sparsity of the original problem data and usually to have fast initial ratio of convergence. This family of algorithms arose from the generalization of the idea presented by João Gonçalves, Robert Storer and Jacek Gondzio to develop the optimal pair adjustment algorithm. This algorithm was developed in its own turn based on the Von Neumann's algorithm. It has interesting properties, such as simplicity and fast initial convergence, but it is not very practical for solving linear problems, since its convergence is very slow. From the computational point of view, our suggestion is not to use the family of algorithms to solve problems of linear programming until optimality, but to exploit its simplicity and its fast initial ratio of convergence and use it together with a infeasible primal-dual interior point method to improve its efficiency. Numerical experiments show that using this family of algorithms with an infeasible primal-dual interior point method improves its performance in the solution of some classes of large-scale linear programming problems. / Doutorado / Doutor em Matemática Aplicada

Cette thèse présente quelques résultats de la théorie des probabilités non commutatives, et traite en particulier des inégalités de martingales dans des algèbres de von Neumann et de leurs espaces de Hardy associés. La première partie démontre un analogue non commutatif de la décomposition de Davis faisant intervenir la fonction carrée. Les arguments classiques de temps d'arrêt ne sont plus valides dans ce cadre, et la preuve se base sur une approche duale. Le deuxième résultat important de cette partie détermine ainsi le dual de l'espace de Hardy conditionnel h_1(M). Ces résultats sont ensuite étendus au cas 1<p<2. La deuxième partie transfère une décomposition atomique pour les espaces de Hardy h_1(M) et H_1(M) aux martingales non commutatives. Des résultats d'interpolation entre les espaces h_p(M) et bmo(M) sont également établis, relativement aux méthodes complexe et réelle d'interpolation. Les deux premières parties concernent des filtrations discrètes. Dans la troisième partie, on introduit des espaces de Hardy de martingales non commutatives relativement à une filtration continue. Les analogues des inégalités de Burkholder/Gundy et de Burkholder/Rosenthal sont obtenues dans ce cadre. La dualité de Fefferman-Stein ainsi que la décomposition de Davis sont également transférées avec succès à cette situation. Les preuves se basent sur des techniques d'ultraproduit et de L_p-modules. Une discussion sur une décomposition impliquant des atomes algébriques permet d'obtenir les résultats d'interpolation attendus / This thesis presents some results of the theory of noncommutative probability. It deals in particular with martingale inequalities in von Neumann algebras, and their associated Hardy spaces. The first part proves a noncommutative analogue of the Davis decomposition, involving the square function. The usual arguments using stopping times in the commutative case are no longer valid in this setting, and the proof is based on a dual approach. The second main result of this part determines the dual of the conditioned Hardy space h_1(M). These results are then extended to the case 1<p<2. The second part proves that an atomic decomposition for the Hardy spaces h_1(M) and H_1(M) is valid for noncommutative martingales. Interpolation results between the spaces h_p(M) and bmo(M) are also established, with respect to both complex and real interpolations. The two first parts concern discrete filtrations. In the third part, we introduce Hardy spaces of noncommutative martingales with respect to a continuous filtration. The analogues of the Burkholder/Gundy and Burkholder/Rosenthal inequalities are obtained in this setting. The Fefferman-Stein duality and the Davis decomposition are also successfully transferred to this situation. The proofs are based on ultraproduct techniques and L_p-modules. A discussion about a decomposition involving algebraic atoms gives the expected interpolation results

The validity of the von-Neumann inequality for commuting $n$ - tuples of $3\times 3$ matrices remains open for $n\geq 3$. We give a partial answer to this question, which is used to obtain a necessary condition for the Carathéodory-Fejérinterpolation problem on the polydisc$\D^n. $ in the special case of $n=2$ (which follows from Ando's theorem as well), this necessary condition is made explicit. We discuss an alternative approach to the Carathéodory-Fejérinterpolation problem, in the special case of $n=2$, adapting a theorem of Korányi and Pukánzsky. As a consequence, a class of polynomials are isolated for which a complete solution to the Carathéodory-Fejér interpolation problem is easily obtained. Many of our results remain valid for any $n\in \mathbb N$, however the computations are somewhat cumbersome. Recall the well known inequality due to Varopoulos, namely, $\lim{n\to \infty}C_2(n)\leq 2 K^\C_G$, where $K^\C_G$ is the complex Grothendieck constant and \[C_2(n)=sup\{\|p(\boldsymbolT)\|:\|p\|_{\D^n,\infty}\leq 1, \|\boldsymbol T\|_{\infty} \leq 1\}.\] Here the supremum is taken over all complex polynomials $p$ in $n$ variables of degree at most $2$ and commuting $n$ - tuples$\boldsymbolT:=(T_1,\ldots,T_n)$ of contractions. We show that \[\lim_{n\to \infty} C_2 (n)\leq \frac{3\sqrt{3}}{4} K^\C_G\] obtaining a slight improvement in the inequality of Varopoulos. We also discuss several finite and infinite dimensional operator space structures on $\ell^1(n) $, $n>1. $

Dans cette thèse je m'intéresse à des propriétés de rigidité de certaines constructions d'algèbres de von Neumann. Ces constructions relient la théorie des groupes et la théorie ergodique au monde des algèbres d'opérateurs. Il est donc naturel de s'interroger sur la force de ce lien et sur la possibilité d'un enrichissement mutuel dans ces différents domaines. Le Chapitre II traite des actions Gaussiennes. Ce sont des actions de groupes discrets préservant une mesure de probabilité qui généralisent les actions de Bernoulli. Dans un premier temps, j'étudie les propriétés d'ergodicité de ces actions à partir d'une analyse de leurs algèbres de von Neumann (voir Theorem II.1.22 et Corollary II.2.16). Ensuite, je classifie les algèbres de von Neumann associées à certaines actions Gaussiennes, à isomorphisme près, en montrant un résultat de W*-Superrigidité (Theorem II.4.5). Ces résultats généralisent des travaux analogues sur les actions de Bernoulli ([KT08,CI10,Io11,IPV13]).Dans le Chapitre III, j'étudie les produits libres amalgamés d'algèbres de von Neumann. Ce chapitre résulte d'une collaboration avec C. Houdayer et S. Raum. Nous analysons les sous-Algèbres de Cartan de tels produits libres amalgamés. Nous déduisons notamment de notre analyse que le produit libre de deux algèbres de von Neumann n'est jamais obtenu à partir d'une action d'un groupe sur un espace mesuré.Enfin, le Chapitre IV porte sur les algèbres de von Neumann associées à des groupes hyperboliques. Ce chapitre est obtenu en collaboration avec A. Carderi. Nous utilisons la géométrie des groupes hyperboliques pour fournir de nouveaux exemples de sous-Algèbres maximales moyennables (mais de type I) dans des facteurs II_1. / The purpose of this dissertation is to put on light rigidity properties of several constructions of von Neumann algebras. These constructions relate group theory and ergodic theory to operator algebras.In Chapter II, we study von Neumann algebras associated with measure-Preserving actions of discrete groups: Gaussian actions. These actions are somehow a generalization of Bernoulli actions. We have two goals in this chapter. The first goal is to use the von Neumann algebra associated with an action as a tool to deduce properties of the initial action (see Corollary II.2.16). The second aim is to prove structural results and classification results for von Neumann algebras associated with Gaussian actions. The most striking rigidity result of the chapter is Theorem II.4.5, which states that in some cases the von Neumann algebra associated with a Gaussian action entirely remembers the action, up to conjugacy. Our results generalize similar results for Bernoulli actions ([KT08,CI10,Io11,IPV13]).In Chapter III, we study amalgamated free products of von Neumann algebras. The content of this chapter is obtained in collaboration with C. Houdayer and S. Raum. We investigate Cartan subalgebras in such amalgamated free products. In particular, we deduce that the free product of two von Neumann algebras is never obtained as a group-Measure space construction of a non-Singular action of a discrete countable group on a measured space.Finally, Chapter IV is concerned with von Neumann algebras associated with hyperbolic groups. The content of this chapter is obtained in collaboration with A. Carderi. We use the geometry of hyperbolic groups to provide new examples of maximal amenable (and yet type I) subalgebras in type II_1 factors.

Dans cette thèse, on s'intéresse à la théorie mesurée des groupes, à l'entropie sofique et aux algèbres d'opérateurs ; plus précisément, on étudie les actions des groupes sur des espaces de probabilités, des propriétés fondamentales de leur entropie sofique (pour des groupes discrets), leurs groupes pleins (pour des groupes Polonais), et les algèbres de von Neumann et leurs sous-algèbres moyennables (pour des groupes à caractère hyperbolique et des réseaux de groupes de Lie). Cette thèse est constituée de trois parties.Dans une première partie j'étudie l'entropie sofique des actions profinies. L'entropie sofique est un invariant des actions mesurées des groupes sofiques défini par L. Bowen qui généralise la notion d'entropie introduite par Kolmogorov. La définition d'entropie sofique nécessite de fixer une approximation sofique du groupe. Nous montrons que l'entropie sofique des actions profinies est effectivement dépendante de l'approximation sofique choisie dans le cas des groupes libres et certains réseaux de groupes de Lie.La deuxième partie est un travail en collaboration avec François Le Maître. Elle est constituée d'un article prépublié dans lequel nous généralisons la notion de groupe plein aux actions préservant une mesure de probabilité des groupes polonais, et en particulier, des groupes localement compacts. On définit une topologie polonaise sur ces groupes pleins et on étudie leurs propriétés topologiques fondamentales, notamment leur rang topologique et la densité des éléments apériodiques.La troisième partie est un travail en collaboration avec Rémi Boutonnet. Elle est constituée de deux articles prépubliés dans lesquels nous considérons la question de la maximalité de la sous-algèbre de von Neumann d'un sous-groupe moyennable maximal, dans celle du groupe ambiant. Nous résolvons la question dans le cas des groupes à caractère hyperbolique en utilisant les techniques de Sorin Popa. Puis, nous introduisons un critère dynamique à la Furstenberg, permettant de résoudre la question pour des sous-groupes moyennables de réseaux des groupes de Lie en rang supérieur. / This dissertation is about measured group theory, sofic entropy and operator algebras. More precisely, we will study actions of groups on probability spaces, some fundamental properties of their sofic entropy (for countable groups), their full groups (for Polish groups) and the amenable subalgebras of von Neumann algebras associated with hyperbolic groups and lattices of Lie groups. This dissertation is composed of three parts.The first part is devoted to the study of sofic entropy of profinite actions. Sofic entropy is an invariant for actions of sofic groups defined by L. Bowen that generalize Kolmogorov's entropy. The definition of sofic entropy makes use of a fixed sofic approximation of the group. We will show that the sofic entropy of profinite actions does depend on the chosen sofic approximation for free groups and some lattices of Lie groups. The second part is based on a joint work with François Le Maître. The content of this part is based on a prepublication in which we generalize the notion of full group to probability measure preserving actions of Polish groups, and in particular, of locally compact groups. We define a Polish topology on these full groups and we study their basic topological properties, such as the topological rank and the density of aperiodic elements. The third part is based on a joint work with Rémi Boutonnet. The content of this part is based on two prepublications in which we try to understand when the von Neumann algebra of a maximal amenable subgroup of a countable group is itself maximal amenable. We solve the question for hyperbolic and relatively hyperbolic groups using techniques due to Popa. With different techniques, we will then present a dynamical criterion which allow us to answer the question for some amenable subgroups of lattices of Lie groups of higher rank.

L'objet de cette thèse est l'étude de la propriété (T) relative à l'espace (ou rigidité au sens de Popa) d'actions de groupes dénombrables sur des espaces de probabilité standards préservant une mesure de probabilité (pmp). Ces dix dernières années, la propriété (T) relative à l'espace a permis de résoudre de nombreux problèmes dans le cadre de la théorie ergodique des actions de groupes et des algèbres de von Neumann. Néanmoins, certains aspects théoriques de cette notion restent largement mystérieux. Une question encore ouverte consiste à déterminer les groupes admettant une action libre ergodique pmp ayant la propriété (T) relative à l'espace. Nous montrons dans cette thèse que les groupes de type fini non-moyennables linéaires sur un corps de caractéristique nulle admettent une action ergodique pmp possédant cette propriété. Si le groupe est à radical résoluble trivial, l'action que nous construisons est aussi libre.Pour ce faire, nous commençons par étudier la stabilité de la propriété (T) relative à l'espace vis-à-vis de différentes constructions d'actions pmp  : produit, restriction, co-induction, induction. Puis, nous donnons une caractérisation de la propriété (T) relative à l'espace dans le cas d'actions pmp sur un espace homogène G/Λ de groupe de Lie p-adique d'un sous-groupe dénombrable Γ du groupe des transformations affines de G stabilisant le réseau Λ. L'action de Γ sur G/Λ a la propriété (T) relative à l'espace si et seulement s'il n'existe pas de mesure de probabilité Γ-invariante sur l'espace projectif de l'algèbre de Lie de G. Par ailleurs, nous étudions le cas d'actions de groupes par automorphismes sur des nilvariétés définies par des graphes finis. / The purpose of this thesis is to study the Kazhdan's property (T) relative to the space (also called rigidity in the sense of Popa) of probability measure preserving actions of countable groups on standard probability measure spaces (p.m.p.).This last decade, some problems in the theory of ergodic theory and von Neumann algebras were solved using the property (T) relative to the space. However, the theoretical aspects of its study remain largely mysterious. An open question asks which groups admit a p.m.p. free and ergodic action which has the property (T) relative to the space. We show in this dissertation that every finitely-generated non-amenable linear groups over a field of characteristic zero admits a p.m.p. ergodic action which has this property. If this group has trivial solvable radical, we prove that these actions can be chosen to be free.In order to obtain these results, we start by investigating natural questions concerning the stability of the property (T) relative to the space through standard constructions : products, restriction, co-induction, induction. Then, we give a criterion for the property (T) relative to the space to hold in the case of p.m.p. actions on homogeneous space G/ Λ of a p-adic Lie group for a countable subgroup Γ of affine transformations of G stabilizing the lattice Λ. The action of Γ on G/Λ has the property (T) relative to the space if and only if the induced action of Γ on the projective space of the Lie algebra of G admits no invariant probability measure.Moreover, we study the case of actions by automorphims on nilvarietes defined by finite graphs.

Dans cette thèse, je m'intéresse à diverses propriétés de rigidité des algèbres de von Neumann. Dans le Chapitre 1, je démontre la solidité relative des produits croisés issus d'actions Bernoulli de type quelconque. Ce résultat repose sur la théorie de la déformation/rigidité de Popa et généralise un théorème de Chifan et Ioana en type II. Comme conséquence, dès que le groupe qui agit est non-moyennable, ces produits croisés sont premiers (n'admettent pas de décomposition non triviale en produit tensoriel de deux facteurs) et la relation d'équivalence associée est solide. Le Chapitre 2 a pour thème les facteurs pleins et les phénomènes de trous spectraux. Je montre notamment que tout facteur plein de type $III$ vérifie une propriété de trou spectral similaire à celle obtenue par Connes dans le cas II_1. Le trou spectral permet d'analyser plus finement la structure de ces facteurs et de leur groupe d'automorphismes. Je généralise ainsi un théorème de Jones en donnant une condition suffisante pour qu'un produit croisé soit plein. Cette condition est de plus nécessaire dans le cas où le groupe qui agit est abélien. Ceci permet de caractériser complètement les facteurs de type III_1 dont le cœur est plein. Dans un travail en collaboration avec C. Houdayer et P. Verraedt, nous montrons aussi qu'un produit tensoriel de deux facteurs pleins est encore plein et nous calculons ses invariants de Connes. Nous obtenons aussi un théorème d'unique décomposition McDuff qui généralise un résultat de Popa dans le cas II_1.Dans le Chapitre 3, je m'intéresse aux facteurs McDuff, i.e. qui ont la propriété d'absorber tensoriellement le facteur hyperfini, ainsi qu'à leur analogue en théorie ergodique, les relations d'équivalences stables. Je donne notamment une nouvelle caractérisation de cette propriété de stabilité qui repose sur un argument de maximalité. Cette caractérisation de type "trou spectral", plus fine que celle connue jusqu'alors, permet de démontrer le résultat de rigidité suivant: un produit direct de deux relations d'équivalences est stable si et seulement si l'une des deux est stable. Le problème similaire pour les facteurs McDuff reste ouvert, mais je donne quelques résultats partiels. / In this dissertation, I study several rigidity properties of von Neumann algebras. In Chapter 1, we prove the relative solidity of Bernoulli crossed products of arbitrary type. This result is based on Popa's deformation/rigidity and generalizes a theorem of Chifan and Ioana in the tracial case. As a consequence, when the acting group is non-amenable, the crossed product is prime (cannot be decomposed nontrivially as a tensor product of two factors) and the associated equivalence relation is solid.In Chapter 2, we study full factors in relation with the spectral gap property. The main result is a spectral gap characterization of full type III factors which is similar to Connes' characterization in the tracial case. This allows us to better understand the structure of these factors and their automorphism group. We generalize a theorem of Jones by giving a sufficient condition for a crossed product to be full. This condition is necessary when the group is abelian. In particular, we obtain a complete characterization of the type III_1 whose core is full. In a joint work with C. Houdayer and P. Verraedt, we show that a tensor product of two full factors is also full and we compute its Connes invariants. We also prove a unique McDuff decomposition theorem that generalizes a result of Popa in the II_1 case. In Chapter 3, we study McDuff factors, i.e. those factors that can absorb tensorially the hyperfinite factor, as well as their counterpart in ergodic theory, the so-called stable equivalence relations. We obtain a new "spectral gap like" characterization of these properties, based on a maximality argument. With this refined characterization, we are able to prove the following rigidity result: a direct product of two stable equivalence relations is stable if and only if one of them is already stable. The analoguous problem on McDuff factors remains open, but we do give some partial results.

In this report, we present some of the results achieved by investigating two-dimensional monomial cellular automata modulo m, where m is a non-zero positive integer. Throughout the experiments, we work with the von Neumann neighbourhood and apply the same local rule based on modular multiplication. The purpose of the study is to examine the behaviour of these cellular automata in three different environments, (i.e. the infinite plane, the finite plane and the torus), by means of elementary number theory. We notice how the distance between each pair of cells with state 0 influences the evolution of the automaton and the convergence of its configurations. Similar impact is perceived when the cells attain the values of Euler's-<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cphi" />function or of integers with common divisors with m, when m &gt; 2. Alongside with the states of the cells, the evolution of the automaton, as well as the convergence of its configurations, are also decided by the values attributed to m, whether it is a prime, a prime power or a multiple of primes and/or prime powers.

This thesis describes methods for transforming applicative programs with the aim of improving their efficiency. The general justification for these techniques is presented via the concept of abstract interpretation. The work can be seen as providing mechanisms to optimise applicative programs for sequential von Neumann machines. The chapters address the following subjects. Chapter 1 gives an overview and gentle introduction to the following technical chapters. Chapter 2 gives an introduction to and motivation for the concept of abstract interpretation necessary for the detailed understanding of the rest of the work. It includes certain theoretical developments, of which I believe the most important is the incorporation of the concept of partial functions into our notion of abstract interpretation. This is done by associating non-standard denotations with functions just as denotational semantics gives the standard denotations. Chapter 3 gives an example of the ease with which we can talk about function objects within abstract interpretive schemes. It uses this to show how a simple language using call-by-need semantics can be augmented with a system that annotates places in a program at which call-by-value can be used without violating the call-by-need semantics. Chapter 4 extends the work of chapter 3 by showing that under some sequentiality restriction, the incorporation of call-by-value for call-by-need can be made complete in the sense that the resulting program will only possess strict functions except for the conditional. Chapter 5 is an attempt to apply the concepts of abstract interpretation to a completely different problem, that of incorporating destructive operators into an applicative program. We do this in order to increase the efficiency of implementation without violating the applicative semantics by introducing destructive operators into our language. Finally, chapter 6 contains a discussion of the implications of such techniques for real languages, and in particular presents arguments whereby applicative languages should be seen as whole systems and not merely the applicative subset of some larger language.

Title: The realization problem for von Neumann regular rings Author: Samuel Mokriš Department: Department of Algebra Supervisor of the master thesis: Mgr. Pavel Růžička, Ph.D., Department of Algebra Abstract: With every unital ring R, one can associate the abelian monoid V (R) of isomor- phism classes of finitely generated projective right R-modules. Said monoid is a conical monoid with order-unit. Moreover, for von Neumann regular rings, it satisfies the Riesz refinement property. In the thesis, we deal with the question, under what conditions an abelian conical re- finement monoid with order-unit can be realized as V (R) for some unital von Neumann regular ring or algebra, with emphasis on countable monoids. Two generalizations of the construction of V (R) to the context of nonunital rings are presented and their interrelation is analyzed. To that end, necessary properties of rings with local units and modules over such rings are devel- oped. Further, the construction of Leavitt path algebras over quivers is presented, as well as the construction of a monoid associated with a quiver that is isomorphic to V (R) of the Leavitt path algebra over the same quiver. These methods are then used to realize directed unions of finitely generated free abelian monoids as V (R) of algebras over any given field. A method...