检索结果-内蒙古大学图书馆

44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Oki, Taihei Univ Tokyo Dept Math Informat Grad Sch Informat Sci & Technol Bunkyo Ku Tokyo Japan

ISBN: (纸本)9781450360845

Differential-algebraic equations (DAEs) are widely used for modeling of dynamical systems. In numerical analysis of DAEs, consistent initialization and index reduction are important preprocessing prior to numerical integration. Existing DAE solvers commonly adopt structural preprocessing methods, which are based on combinatorial optimization. Unfortunately, the structural methods fail if the DAE has numerical or symbolic cancellations. For such DAEs, methods have been proposed to modify them to other DAEs to which the structural methods are applicable. The modification methods are based on the combinatorial relaxation technique. Existing modification methods, however, work only for a class of DAEs that are linear or close to linear. This paper proposes two modification methods for nonlinear DAEs: the substitution method and the augmentation method. Both methods are based on the combinatorial relaxation approach and are applicable to a large class of nonlinear DAEs. The substitution method symbolically solves equations for some derivatives based on the implicit function theorem and substitutes the solution back into the system. Instead of solving equations, the augmentation method modifies DAEs by appending new variables and equations. The augmentation method has advantages that the equation solving is not needed and the sparsity of DAEs is retained. It is shown in numerical experiments that both methods successfully modify high-index DAEs that the DAE solver in MATLAB cannot handle.

关键词： differential-algebraic equations consistent initialization index reduction implicit function theorem combinatorial relaxation combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

A measure of the local connectivity between graph vertices

A measure of the local connectivity between graph vertices

引用

International Conference on Computational Science (ICCS) on the Ascent of Computational Excellence

作者： Chen, Jie Safro, Ilya Argonne Natl Lab Math & Comp Sci Div Argonne IL 60439 USA

Measuring the connectivity strength between a pair of vertices in a graph is one of the most vital concerns in numerous computational graph problems. In this paper we propose a local measure, together with an efficient algorithm that is scalable and parallelizable. In the heart of the algorithm is an iterative process that propagates and refines random values associated with each vertex. The connectivity measure hence defined, named algebraic distance, is the absolute difference between two values after a small number of iterations. This process is inspired by the bootstrap algebraic multigrid (BAMG), where a similar process is employed to expose connections between variables and to determine their role in convergence of a multigrid solver. We show convergence properties of the proposed measure, and provide a mutually reinforcing model to explain why the algebraic distances meaningfully measure the connectivity in a local sense. The practical effectiveness of the proposed measure is demonstrated on several computational (hyper)graph problems.

关键词： connectivity algebraic distance combinatorial scientific computing computational graph problems

来源：评论

学校读者我要写书评

暂无评论

Structural Preprocessing Method for Nonlinear Differential-Algebraic Equations Using Linear Symbolic Matrices 49

Structural Preprocessing Method for Nonlinear Differential-A...

引用

International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Oki, Taihei Song, Yujin Univ Tokyo Tokyo Japan

ISBN: (纸本)9798400706967

Differential-algebraic equations (DAEs) have been used in modeling various dynamical systems in science and engineering. There are several preprocessing methods that are needed before performing numerical simulations for DAEs, such as consistent initialization and index reduction. Preprocessing methods that use structural information on DAEs run fast and are widely used. Unfortunately, structural preprocessing methods may fail when the system Jacobian, which is a functional matrix, derived from the DAE is singular. To transform a DAE with a singular system Jacobian into a nonsingular system, several structural regularization methods have been proposed. Most of all existing structural regularization methods rely on symbolic computation to eliminate the system Jacobian for finding a certificate of singularity, resulting in much computational time. Iwata-Oki-Takamatsu (2019) proposed a method (IOT-method) to find a certificate without symbolic computations. The IOT method approximates the system Jacobian by a simpler symbolic matrix, called a layered mixed matrix, which admits a fast combinatorial algorithm for singularity testing. Although the IOT method runs fast, it often overlooks the singularity of the system Jacobian since the approximation largely discards algebraic relationships among entries in the original system Jacobian. In this study, we propose a new structural regularization method extending the idea of the IOT method. Instead of layered mixed matrices, our method approximates the system Jacobian by more expressive symbolic matrices, called rank-1 coefficient mixed (1CM) matrices. This makes our method more widely applicable than the existing method. We give a fast combinatorial algorithm for finding a singularity certificate of 1CM-matrices, making our structural regularization method free from symbolic elimination. Our method is also advantageous in that it globally preserves the solution set to the DAE. Through numerical experiments, we confirmed that

关键词： differential-algebraic equations initial value problem index reduction combinatorial relaxation linear symbolic matrices combinatorial matrix theory combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Interactively Exploring the Connection between Bidirectional Compression and Star Bicoloring

Interactively Exploring the Connection between Bidirectional...

引用

15th Annual International Conference on Computational Science (ICCS)

作者： Rostami, M. Ali Buecker, H. Martin Univ Jena Inst Comp Sci Jena Germany

The connection between scientific computing and graph theory is detailed for a problem called bidirectional compression. This problem consists of finding a pair of seed matrices in automatic differentiation. In terms of graph theory, the problem is nothing but finding a star bicoloring. An interactive educational module is designed and implemented to illustrate the connection between bidirectional compression and star bicoloring. The web-based module is intended to be used in the classroom to illustrate the intricate nature of this combinatorial problem.

关键词： Graph coloring sparse Jacobian automatic differentiation EXPLAIN interactive learning combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Preconditioning Jacobian Systems by Superimposing Diagonal Blocks 1

引用

20th Annual International Conference on Computational Science (ICCS)

作者： Rostami, M. Ali Buecker, H. Martin Friedrich Schiller Univ Jena Inst Comp Sci D-07737 Jena Germany Michael Stifel Ctr Jena Data Driven & Simulat Sci D-07737 Jena Germany

ISBN: (数字)9783030504175

ISBN: (纸本)9783030504175;9783030504168

Preconditioning constitutes an important building block for the solution of large sparse systems of linear equations. If the coefficient matrix is the Jacobian of some mathematical function given in the form of a computer program, automatic differentiation enables the efficient and accurate evaluation of Jacobian-vector products and transposed Jacobian-vector products in a matrix-free fashion. Standard preconditioning techniques, however, typically require access to individual nonzero elements of the coefficient matrix. These operations are computationally expensive in a matrix-free approach where the coefficient matrix is not explicitly assembled. We propose a novel preconditioning technique that is designed to be used in combination with automatic differentiation. A key element of this technique is the formulation and solution of a graph coloring problem that encodes the rules of partial Jacobian computation that determines only a proper subset of the nonzero elements of the Jacobian matrix. The feasibility of this semi-matrix-free approach is demonstrated on a set of numerical experiments using the automatic differentiation tool ADiMat.

关键词： combinatorial scientific computing Partial Jacobian computation Partial graph coloring Sparsity exploitation ADiMat

来源：评论

学校读者我要写书评

暂无评论

An interactive environment to manipulate large graphs

An interactive environment to manipulate large graphs

引用

32nd IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Gilbert, John R. Shah, Viral Reinhardt, Steven Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Silicon Graph Inc Fremont CA 94538 USA

ISBN: (纸本)1424407281

Interactive environments such as MATLAB and STAR-P have made numerical computing tremendously accessible to engineers and scientists. They allow people who are not well-versed in the art of numerical computing to nonetheless reap the benefits of numerical computing. The same is not true in general for combinatorial computing. Often, many interesting problems require a mix of numerical and combinatorial computing. Tools developed for numerical computing - such as sparse matrix algorithms - can also be used to develop a comprehensive infrastructure for graph algorithms. We describe the current status of our effort to build a comprehensive infrastructure for operations on large graphs in an interactive parallel environment such as STAR-P.

关键词： combinatorial scientific computing large graphs pattern discovery interactive

来源：评论

学校读者我要写书评

暂无评论

Reformulating a Breadth-First Search Algorithm on an Undirected Graph in the Language of Linear Algebra

Reformulating a Breadth-First Search Algorithm on an Undirec...

引用

International Conference on Mathematics and Computers in Sciences and in Industry (MCSI)

作者： Buecker, H. Martin Sohr, Christian Univ Jena Dept Math & Comp Sci Inst Comp Sci D-07737 Jena Germany

ISBN: (纸本)9781479943241

The formulation of algorithms from sparse linear algebra is often based on suitable concepts from graph theory. However, conversely, the formulation of algorithms from graph theory is rarely based on suitable concepts from sparse linear algebra. Here, we present an illustrating example of a standard graph algorithm that is expressed in the language of sparse linear algebra. More precisely, we reformulate a breadth-first search (BFS) algorithm on an undirected graph using sparse matrix-vector products. In addition, we demonstrate that the performance of this matrix-based BFS algorithm on an Intel Core 2 Duo CPU E8400 is improved as compared to a traditional graph-based BFS algorithm.

关键词： combinatorial scientific computing linear algebra graph theory breadth-first search

来源：评论

学校读者我要写书评

暂无评论

On matchings and related problems in graphs, hypergraphs, and doubly stochastic matrices: Sur les couplages et les problèmes liés dans les graphes, les hypergraphes et les matrices doublement stochastiques

On matchings and related problems in graphs, hypergraphs, an...

引用

作者： Panagiotas, Ioannis

学位级别：博士

Cette thèse examine quatre problèmes différents et connexes qui se posent dans le domaine du calcul scientifique combinatoire (CSC). Le lien de connexion entre les quatre problèmes examinés est le problème fondamental des couplages, qui cherche le plus grand ensemble d’arêtes disjointes dans un graphe ou un hypergraphe. Ces problèmes sont ceux du couplage de cardinalité maximale dans les graphes et dans les hypergraphes, l’estimation du nombre de couplages parfaits, et la décomposition de Birkhoff–von Neumann des matrices bistochastiques. L’étude de ces problèmes est motivée par leur utilité dans plusieurs domaines d’*** examinons les quatre problèmes à la fois théoriquement et expérimentalement. L’accent mis sur la théorie nous permet de discuter, d’analyser et de prouver les propriétés des algorithmes examinés, tandis que le côté expérimental de la thèse démontre les améliorations et les avantages possibles de l’utilisation des algorithmes et des solutions proposés. This thesis investigates four different and related problems that arise in the area of combinatorial scientific computing (CSC). The connecting link between the four examined problems is the fundamental problem of matching, which asks for the largest set of disjoint edges in a graph or hypergraph. These problems are that of maximum cardinality matching in graphs and hypergraphs, the estimation of the number of perfect matchings in graphs, and the Birkhoff–von Neumann decomposition of doubly stochastic matrices. The study of these problems is motivated by their usefulness in several domains and *** examine the four problems both theoretically as well as experimentally. The focus in theory allows us to discuss, analyze, and prove properties of the examined algorithms, while the experimental side of the thesis demonstrates the possible improvements and benefits of using the proposed algorithms and solutions.

关键词： Calcul scientifique combinatoire Graphes Hypergraphes Algorithmes Matrices bistochastiques Couplage Heuristiques combinatorial scientific computing Graphs Hypergraphs Algorithms Doubly stochastic matrices Matching Heuristics

来源：评论

学校读者我要写书评

暂无评论

A RECURSIVE BIPARTITIONING ALGORITHM FOR PERMUTING SPARSE SQUARE MATRICES INTO BLOCK DIAGONAL FORM WITH OVERLAP

引用

SIAM JOURNAL ON scientific computing 2013年第1期35卷 C99-C121页

作者： Acer, Seher Kayaaslan, Enver Aykanat, Cevdet Bilkent Univ Dept Comp Engn Ankara Turkey

We investigate the problem of symmetrically permuting a square sparse matrix into a block diagonal form with overlap. This permutation problem arises in the parallelization of an explicit formulation of the multiplicative Schwarz preconditioner and a more recent block overlapping banded linear solver as well as its application to general sparse linear systems. In order to formulate this permutation problem as a graph theoretical problem, we define a constrained version of the multiway graph partitioning by vertex separator (GPVS) problem, which is referred to as the ordered GPVS (oGPVS) problem. However, existing graph partitioning tools are unable to solve the oGPVS problem. So, we also show how the recursive bipartitioning framework can be utilized for solving the oGPVS problem. For this purpose, we propose a left-to-right bipartitioning approach together with a novel vertex fixation scheme so that existing 2-way GPVS tools that support fixed vertices can be effectively and efficiently utilized in the recursive bipartitioning framework. Experimental results on a wide range of matrices confirm the validity of the proposed approach.

关键词： sparse square matrices block diagonal form with overlap graph partitioning by vertex separator recursive bipartitioning partitioning with fixed vertices combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

1.5D PARALLEL SPARSE MATRIX-VECTOR MULTIPLY

引用

SIAM JOURNAL ON scientific computing 2018年第1期40卷 C25-C46页

作者： Kayaaslan, Enver Aykanat, Cevdet Ucar, Bora NTENT Inc 1808 Aston Ave Carlsbad CA 92008 USA Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey ENS Lyon CNRS 46 Allee Italie F-69364 Lyon France ENS Lyon CNRS LIP UMR5668INRIAUCBL 46 Allee Italie F-69364 Lyon France

There are three common parallel sparse matrix-vector multiply algorithms: 1D row-parallel, 1D column-parallel, and 2D row-column-parallel. The 1D parallel algorithms offer the advantage of having only one communication phase. On the other hand, the 2D parallel algorithm is more scalable, but it suffers from two communication phases. Here, we introduce a novel concept of heterogeneous messages where a heterogeneous message may contain both input-vector entries and partially computed output-vector entries. This concept not only leads to a decreased number of messages but also enables fusing the input- and output-communication phases into a single phase. These findings are exploited to propose a 1.5D parallel sparse matrix-vector multiply algorithm which is called local row-column-parallel. This proposed algorithm requires a constrained fine-grain partitioning in which each fine-grain task is assigned to the processor that contains either its input vector entry, its output-vector entry, or both. We propose two methods to carry out the constrained fine-grain partitioning. We conduct our experiments on a large set of test matrices to evaluate the partitioning qualities and partitioning times of these proposed 1.5D methods.

关键词： sparse matrix partitioning parallel sparse matrix-vector multiplication directed hypergraph model bipartite vertex cover combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：