International audience

Let P be a family of dipaths. The load of an arc is the number of dipaths containing this arc. Let pi(G, P) be the maximum of the load of all the arcs and let w(G, P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arc-disjoint. Let G be a DAG (directed acyclic graph). An internal cycle is an oriented cycle such that all the vertices have at least one predecessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). Here we prove that if G is a DAG without internal cycle, then for any family of dipaths P, w(G, P) = pi(G, P). On the opposite we give examples of DAGs with internal cycles such that the ratio between w(G, P) and pi(G, P) cannot be bounded. We also consider an apparently new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPP-DAGs. For these UPP-DAGs we show that the load is equal to the maximum size of a clique of the conflict graph. We show that if an UPP-DAG has only one internal cycle, then for any family of dipaths w(G, P) = lceilpi(G, P)rceil and we exhibit an UPP-DAG and a family of dipaths reaching the bound. We conjecture that the ratio between w(G, P) and pi(G, P) cannot be bounded.

Finding the nonzero structures of the lower and upper triangular factors of an unsymmetric sparse matrix A is an important problem in the field of sparse matrix computations. Complementing previous research on sequential algorithms, we develop a parallel algorithm by appropriately intertwining a fully concurrent algorithm with an experimentally proved efficient algorithm (both algorithms are previous art). The resulting algorithm, intended to use with out-of-core matrices, leads to sensitive improvements in memory usage.

In this paper we present several improvements of widely used parallel LU factorization methods on sparse matrices. First we introduce the LU elimination forest and then we characterize the L, U factors in terms of their corresponding LU elimination forest. This characterization can be used as a compact storage scheme of the matrix as well as of the task dependence graph. To improve the use of BLAS in the numerical factorization, we perform a postorder traversal of the LU elimination forest, thus obtaining larger supernodes. To expose more task parallelism for a sparse matrix, we build a more accurate task dependence graph that includes only the least necessary dependences. Experiments compared favorably our methods against methods implemented in the S* environment on the SGI's Origin2000 multiprocessor.

Task graph scheduling has been found effective in performance prediction and optimization of parallel applications. A number of static scheduling algorithms have been proposed for task graph execution on distributed memory machines. Such an approach cannot be adapted to changes in values of program parameters and the number of processors and also it cannot handle large task graphs. In this paper, we model parallel computation using parameterized task graphs which represent coarse-grain parallelism independent of the problem size. We present a scheduling algorithm for a parameterized task graph which first derives symbolic linear clusters and then assigns task clusters to processors. The runtime system executes clusters on each processor in a multi-threaded fashion. We evaluate our method using various compute-intensive kernels that can be found in scientific applications.

The DAG based task graph model has been found effective in scheduling for performance prediction and optimization of parallel applications. However the scheduling complexity and solution normally depend on the problem size. We propose a symbolic scheduling scheme for a parameterized task graph which models coarse grain DAG parallelism, independent of the problem size. The algorithm first derives symbolic clusters to a group of tasks in order to minimize communication while preserving parallelism, and then it evenly assigns task clusters to processors. The run time system executes clusters on each processor in a multithreaded fashion. The paper also presents preliminary experimental results to demonstrate the effectiveness of our techniques.

We study the complexity of the parallel Givens factorization of a square matrix of size n on a shared memory architecture composed with p identical processors (coarse grained EREW PRAM).We show how to construct an asymptotically optimal algorithm.We deduce that the time complexity is equal to:and that the minimum number of processors in order to compute the Givens factorization inThese results complete previous analysis presented in the case where the number of processors is unlimited.

We have studied various implementations of iterative polynomial root finding methods on a distributed memory multicomputer. These methods are based on the construction of a sequence of approximations that converge to the set of zeros. The synchronous version consists in sharing the computation of the next iterate among the processors and updating their data through a total exchange of their results. In order to decrease the communication cost, we introduce asynchronous versions. The computation of the next iterate is still shared among the processor, but the updating is done by using only nearest neighbor communications. We prove that under weak conditions, these asynchronous versions are still locally convergent, even if their convergence orders are reduced. We analyze the behavior of the asynchronous methods in function of their delay, the topology of the interconnection network, and the elementary computation and communication times. We have implemented and compared these methods on a hypercube multicomputer.>

A parallel algorithm for generating all the k! permutations of kPk for every (1 ≤k ≤ n) is presented. The architecture consists of a linear processor array with n elements. The kth processor receives a permutation p of k–1Pk–1 from the (k — 1 )th processor and intercalates k at all the k possible positions of the sequence p, one at a time. After each intercalation it sends the permutation obtained to the (k + l)th processor and also outputs it. In this way the nth processor outputs all the n! permutations of nPn in (n + n!) units of time and our profit are all the kPk(1 ≤k < N) which output is included in that time. The network is VLSI implementable and fault tolerant. It is shown how to find the position of a given permutation and how to obtain the permutation of a given position, where position refers to the generation order of the permutations by each processor. With a simple modification in the algorithm performed by the processors, the network is able to generate combinations.

We describe a general VLSI architecture for the computation of arithmetic expressions including floating-point trancendental functions. This architecture is divided in three parts: a communication machine, the control part of a computation machine and the operative part of this computation machine. In order to compute the most usual trancendental functions, we introduced some general algorithms, presented briefly here, including as a particular case the CORDIC scheme. Our major architecture goals were regularity, parametrization and automatic design. The final chip is designed in a 2-Alu CMOS technology, and its name is FELIN (“Fonctions ELémentaires INtégrées is the french for integrated elementary functions”). This work was supported in part by the GRECO C3and the GCIS of the French CNRS.

An optimal algorithm to perform the parallel QR decomposition of a dense matrix of size N is proposed. It is deduced that the complexity of such a decomposition is asymptotically 2 N , when an unlimited number of processors is available.

Key Words and Phrases nonlinear equations, numer)cal solut,on, Brent's method CR Categories

article Numerical Solution of Nonlinear Equations Share on Authors: Jorge J. Moré Applied Mathematics Division, Argonne National Laboratory, 9700, South Cass Ave., Argonne, IL Applied Mathematics Division, Argonne National Laboratory, 9700, South Cass Ave., Argonne, ILView Profile , Michel Y. Cosnard Mathématiques Appliquées-Informatique, Universite Scientifique et Médicale de Grenoble, Boite Postale 53, 38041 Grenoble Cédex, France Mathématiques Appliquées-Informatique, Universite Scientifique et Médicale de Grenoble, Boite Postale 53, 38041 Grenoble Cédex, FranceView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 5Issue 1March 1979 pp 64–85https://doi.org/10.1145/355815.355820Published:01 March 1979 87citation2,098DownloadsMetricsTotal Citations87Total Downloads2,098Last 12 Months37Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access