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

2009, Volume 8, Issue 2

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.