ANALYSIS OF THE 2-SUM PROBLEM AND THE SPECTRAL ALGORITHM

Authors

  • Alexander Kolomiychuk

DOI:

https://doi.org/10.47839/ijc.8.2.676

Keywords:

2-sum problem, Spectral Algorithm, Fiedler vector, Laplacian of a graph, graph layout problems, sparse matrices, spectral graph theory.

Abstract

This paper presents the analysis of the 2-sum problem and the spectral algorithm. The spectral algorithm was proposed by Barnard, Pothen and Simon in [1]; its heuristic properties have been advocated by George and Pothen in [4] by formulation of the 2-sum problem as a Quadratic Assignment Problem. In contrast to that analysis another approach is proposed: permutations are considered as vectors of Euclidian space. This approach enables one to prove the bound results originally obtained in [4] in an easier way. The geometry of permutations is considered in order to explain what are ‘good’ and ‘pathological’ situations for the spectral algorithm. Upper bounds for approximate solutions generated by the spectral algorithm are proved. The results of numerical computations on (graphs of) large sparse matrices from real-world applications are presented to support the obtained results and illustrate considerations related to the ‘pathological’ cases.

References

S. T. Barnard, A. Pothen, H. D. Simon. A spectral algorithm for envelope reduction of sparse matrices. Numer. Linear Algebra Appl. 2, No.4, 317-334 (1995).

M. Fiedler. Algebraic connectivity of graphs. Czech. Math. J. 23(98), 298-305 (1973).

M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25(100), 619-633 (1975).

J. A. George, A. Pothen. An analysis of spectral envelope reduction via quadratic assignment problems. SIAM J. Matrix Anal. Appl. 18, No.3, 706-732 (1997).

B. Hendrickson, R. Leleand. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16, 452-469 (1995).

M. Juvan, B. Mohar. Optimal linear labeling and eigenvalues of graphs. Discr. Appl. Math. 36, 153-168 (1992).

B. Mohar, S. Poljak. Eigenvalues in combinatorial optimization. Combinatorial and Graph-Theoretical Problems in Linear Algebra. IMA Volumes in Mathematics and its applications, Vol. 50, Springer-Verlag (1993).

A. Pothen, H. D. Simon, K. P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 430-452 (1990).

Tim Davis: University of Florida Sparse Matrix Collection. (http://www.cise.ufl.edu/research/ sparse/matrices/)

Downloads

Published

2014-08-01

How to Cite

Kolomiychuk, A. (2014). ANALYSIS OF THE 2-SUM PROBLEM AND THE SPECTRAL ALGORITHM. International Journal of Computing, 8(2), 139-148. https://doi.org/10.47839/ijc.8.2.676

Issue

Section

Articles