๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel algorithm for the computation of characteristic polynomials of chemical graphs

โœ Scribed by P. Venuvanalingam; P. Thangavel

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
413 KB
Volume
12
Category
Article
ISSN
0192-8651

No coin nor oath required. For personal study only.

โœฆ Synopsis

A parallel algorithm is developed for the f i t time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n9) processors whereas the sequential algorithm takes O(n4) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens-Householder methods.

๐Ÿ“œ SIMILAR VOLUMES

Computer generation of the characteristi
Computer generation of the characteristic polynomials of chemical graphs
โœ K. Balasubramanian ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 497 KB

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of ver

An Accurate and Efficient Algorithm for
An Accurate and Efficient Algorithm for the Computation of the Characteristic Polynomial of a General Square Matrix
โœ S. Rombouts; K. Heyde ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 99 KB

An algorithm is presented for the efficient and accurate computation of the coefficients of the characteristic polynomial of a general square matrix. The algorithm is especially suited for the evaluation of canonical traces in determinant quantum Monte-Carlo methods.

Method for construction of characteristi
Method for construction of characteristic polynomials via graph linearization
โœ Kakali Datta; Asok K. Mukherjee ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 157 KB ๐Ÿ‘ 1 views

A new method for construction of characteristic polynomials CP of complicated graphs having arbitrary edge and vertex weights has been developed. The method first converts the graph into isospectral linear chains with weighted vertices and edges and then builds up the CP coefficients recursively. Tw

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
โœ Jens Lagergren ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem ลฝ 3 . ลฝ. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-ลฝ 2 . position algorithm is O O n log n . The tree-decomposi

Parallel implementation of a ray tracing
Parallel implementation of a ray tracing algorithm for distributed memory parallel computers
โœ Lee, Tong-Yee; Raghavendra, C. S.; Nicholas, John B. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 145 KB ๐Ÿ‘ 3 views

Ray tracing is a well known technique to generate life-like images. Unfortunately, ray tracing complex scenes can require large amounts of CPU time and memory storage. Distributed memory parallel computers with large memory capacities and high processing speeds are ideal candidates to perform ray tr