8 results on '"Uçar, Bora"'
Search Results
2. Algorithms and data structures for hyperedge queries
- Author
-
Bertrand, Jules, Dufossé, Fanny, Uçar, Bora, École normale supérieure - Lyon (ENS Lyon), Data Aware Large Scale Computing (DATAMOVE ), Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Inria Grenoble Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Grenoble Alpes (UGA), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
- Subjects
hypergraphs ,Hachage ,perfect hashing ,Hashing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,hypergraphes ,hachage parfait - Abstract
Revised version May 2021; We consider the problem of querying the existence of hyperedges in hypergraphs. More formally, we are given a hypergraph, and we need to answer queries of the form "does the following set of vertices form a hyperedge in the given hypergraph?''. Our aim is to set up data structures based on hashing to answer these queries as fast as possible. We propose an adaptation of a well-known perfect hashing approach for the problem at hand.We analyze the space and run time complexity of the proposed approach, and experimentally compare it with the state of the art hashing-based solutions. Experiments demonstrate that the proposed approach has the shortest query response time than the other considered alternatives, while having a larger construction time than some of the alternatives.; Nous considérons le problème de requêtes d'existences d'hyperarêtes dans des hypergraphes. Plus formellement, pour un hypergraphe donné, nous devons répondre à des requêtes de la forme "est-ce que l'ensemble de sommets suivant forme une hyperarête de l'hypergraphe?". Notre objectif est de mettre en place une structure de donnée basée sur du hachage pour répondre à ces requêtes le plus rapidement possible. Nous proposons une adaptation d'une approche bien connue de hachage parfait pour notre problème. Nous analysons la complexité en temps et en espace de cette approche, et nous la comparons expérimentalement à des solutions de l'état de l'art basées sur le hachage. Les expériences démontrent que cette approche a un temps de réponse aux requêtes plus court que les alternatives considérées, pour un temps de construction plus long que certaines des alternatives.
- Published
- 2021
3. Partitionnement, couplage et permutation: Calcul scientifique combinatoire sur des matrices et des tenseurs
- Author
-
Uçar, Bora, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), ENS de Lyon, Nadia Brauner, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
graphs ,Matrices creuses ,sparse tensors ,hypergraphs ,tenseurs creux ,graphes ,Sparse matrices ,[INFO]Computer Science [cs] ,hypergraphse - Abstract
This HDR investigates three classes of problems at the interplay of discrete algorithms, combinatorial optimization, and numerical methods. The three problem classes are that of partitioning, matching, and ordering.Partitioning problems arise in task decomposition for parallel computing, where load balance and low communication cost are two objectives. We discuss acyclic partitioning of directed acyclic graphs and hypergraphs. While our contributions for the former problem concern combinatorial tools for the desired partitioning objectives and constraints, those for the second problem concern the use of hypergraph partitioning tools for efficient tensor decomposition in distributed memory systems.Matching problems arise in settings where agents compete for exclusive access to resources. We present approximation algorithms for matchings in graphs and effective heuristics for finding matchings in hypergraphs. We also investigate the problem of finding Birkhoff--von Neumann decompositions with a small number of permutation matrices and present complexity results and theoretical insights into this problem. Ordering problems arise when one wants to permute sparse matrices and tensors into desirable forms. We propose heuristics to permute sparse matrices into special forms to reduce the height of the resulting elimination tree. We also propose heuristics to cluster nonzeros of a given sparse tensor around the diagonal in order to improve the performance of certain tensor operations.The general research area is called combinatorial scientific computing (CSC). In CSC, the contributions have practical and theoretical flavor. For all problems discussed in this document, we have the design, analysis, and implementation of algorithms along with many experiments. The theoretical results are included in this document, some with proofs; the reader is invited to the original papers for the omitted proofs. A similar approach is taken for presenting the experiments. While most results for observing theoretical findings in practice are included, the reader is referred to the original papers for some other results (e.g., run time analysis).
- Published
- 2019
4. Seyrek dikdörtgensel matrislerin AATx (A A üssü T x)'in paralel işlemcilerde hesaplanabilmesi için parçalanması
- Author
-
Uçar, Bora, Aykanat, Cevdet, and Diğer
- Subjects
Matrices ,Computational Hypergraph Model ,Partitions (Mathematics) ,Communication ,Communication Hypergraph Model ,Hypergraph ,Hypergraph Partitioning ,Hypergraphs ,Sparse Rectangular Matrices ,Computer Engineering and Computer Science and Control ,QA165 .U23 1999 ,Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol - Abstract
IV ÖZET SEYREK DİKDÖRTGENSEL MATRİSLERİN AATx'W PARALEL İŞLEMCİLERDE HESAPLANABİLMESİ İÇİN PARÇALANMASI Bora Uçar Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Doc. Dr. Cevdet Aykanat Eylül, 1999 Birçok bilimsel uygulama, bir seyrek dikdörtgensel matrisin bir vektör ve de aynı matrisin transpozunun bir başka vektör ile çarpılmasını içermektedir. Şimdiye kadar kullanılan çizge ve hiperçizge parçalanması algoritmalarında toplam haberleşme hacmi azaltılırken işlemciler arasındaki işlemsel denge, ma trisin tek boyutlu ayrıştırılması ile yakalanmaya çalışılmıştır. Bu tezde, toplam haberleşme sayısı ve hacmi iki yaklaşımla azaltılmaya çalışılmıştır. Genel haberleşme yaklaşımındaki birleşik haberleşme hacminin azaltılması problemi, matrislerin tek sınırlı çarpraz bloklar haline getirilmesi problemine dönüştü rülmüştür. Bu yaklaşımdaki birleşik ve toplam haberleşme sayısı paralel iş lemcilerin bağlantısına bağlı olup değiştirilememektedir. Kişiselleştirilmiş ha berleşme yaklaşımındaki toplam haberleşme sayısı ve hacmi iki aşamada azal tılmıştır. Birinci aşamada, toplam haberleşme hacmi azaltılırken işlemsel denge sağlanılmıştır. ikinci aşamada, önerilen haberleşme hiperçizgesi yardımı ile toplam haberleşme sayısı azaltılırken işlemciler arasında haberleşme işi dengesi sağlanmaya çalışılmıştır. Sunulan yöntemler birçok matris üzerinde sınanmış ve iyi yönde sonuçlar elde edilmiştir. Anahtar kelimeler: Seyrek dikdörtgensel matrisler, hesap hiperçizgesi, haber leşme hiperçizgesi, hiperçizge parçalama. Ill ABSTRACT PARTITIONING SPARSE RECTANGULAR MATRICES FOR PARALLEL COMPUTING OF AATx Bora Uçar M.S. in Computer Engineering and Information Science Supervisor: Asoc. Prof. Dr. Cevdet Aykanat Spetember, 1999 Many scientific applications involve repeated sparse matrix- vector and matrix- transpose- vector product computations. Graph and hypergraph partitioning based approaches used in the literature aim at minimizing the total commu nication volume while maintaining computational load balance through one dimensional partitioning of sparse matrices. In this thesis, we consider two approaches which consider minimizing both the total message count and com munication volume while maintaining balance on the communication loads of the processors. Two communication schemes are investigated for the fold and expand operations needed in the parallel algorithm. For the global communica tion scheme, we show that the problem of minimizing concurrent communica tion volume can be formulated as the problem of permuting the sparse matrix into a singly-bordered block-diagonal form, where the total and concurrent message count is determined by the interconnection topology. For the person alized communication scheme, a two stage approach is proposed. In the first stage, the total communication volume is minimized while maintaining balance on the computational loads of the processors. In the second stage, a novel com munication hypergraph model is proposed which enables the minimization of the total message count while maintaining balance on the communication loads of the processors through hypergraph-partitioning-like methods. The solution methods are tested on various matrices and results, which are quite attractive in terms of solution quality and running times, are obtained. Key words: Sparse Rectangular Matrices, Computational Hypergraph Model, Communication Hypergraph Model, Hypergraph Partitioning. 74
- Published
- 1999
5. A Matrix Partitioning Interface to PaToH in MATLAB
- Author
-
Uçar, Bora, Çatalyürek, Ümit V., and Aykanat, Cevdet
- Subjects
- *
COMPUTER interfaces , *HYPERGRAPHS , *SPARSE matrices , *PARALLEL algorithms , *PARTITIONS (Mathematics) , *RECURSIVE functions , *ORTHOGONALIZATION - Abstract
Abstract: We present the PaToH MATLAB Matrix Partitioning Interface. The interface provides support for hypergraph-based sparse matrix partitioning methods which are used for efficient parallelization of sparse matrix–vector multiplication operations. The interface also offers tools for visualizing and measuring the quality of a given matrix partition. We propose a novel, multilevel, 2D coarsening-based 2D matrix partitioning method and implement it using the interface. We have performed extensive comparison of the proposed method against our implementation of orthogonal recursive bisection and fine-grain methods on a large set of publicly available test matrices. The conclusion of the experiments is that the new method can compete with the fine-grain method while also suggesting new research directions. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF
6. PARTITIONING SPARSE MATRICES FOR PARALLEL PRECONDITIONED ITERATIVE METHODS.
- Author
-
Uçar, Bora and Aykanat, Cevdet
- Subjects
- *
ITERATIVE methods (Mathematics) , *PARTITIONS (Mathematics) , *SPARSE matrices , *GENERALIZED inverses of linear operators , *MATRICES (Mathematics) , *HYPERGRAPHS - Abstract
This paper addresses the parallelization of the preconditioned iterative methods that use explicit preconditioners such as approximate inverses. Parallelizing a full step of these methods requires the coefficient and preconditioner matrices to be well partitioned. We first show that different methods impose different partitioning requirements for the matrices. Then we develop hypergraph models to meet those requirements. In particular, we develop models that enable us to obtain partitionings on the coefficient and preconditioner matrices simultaneously. Experiments on a set of unsymmetric sparse matrices show that the proposed models yield effective partitioning results. A parallel implementation of the right preconditioned BiCGStab method on a PC cluster verifies that the theoretical gains obtained by the models hold in practice. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
7. Hypergraph partitioning for multiple communication cost metrics: Model and methods.
- Author
-
Deveci, Mehmet, Kaya, Kamer, Uçar, Bora, and Çatalyürek, Ümit V.
- Subjects
- *
HYPERGRAPHS , *MICROPROCESSORS , *PARALLEL programming , *BIT rate , *LOAD balancing (Computer networks) , *COMPARATIVE studies - Abstract
We investigate hypergraph partitioning-based methods for efficient parallelization of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
8. Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices
- Author
-
Aykanat, Cevdet, Cambazoglu, B. Barla, and Uçar, Bora
- Subjects
- *
HYPERGRAPHS , *ALGORITHMS , *GRAPH theory , *FUZZY hypergraphs - Abstract
Abstract: -way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct -way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct -way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.