| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Unified Framework for Numerical and Combinatorial Computing
March/April 2008 (vol. 10 no. 2)
pp. 20-25
A rich variety of tools help researchers with high-performance numerical computing, but few tools exist for large-scale combinatorial computing. The authors describe their efforts to build a common infrastructure for numerical and combinatorial computing by using parallel sparse matrices to implement parallel graph algorithms.
1. G. Birkhoff and A. George, "Elimination by Nested Dissection," SIAM J. Numerical Analysis, vol. 10, no. 2, 1973, pp. 345–363.
2. T.F. Coleman, A. Edenbrandt, and J.R. Gilbert, "Predicting Fill for Sparse Orthogonal Factorization," J. ACM, vol. 33, no. 3, 1986, pp. 517–532.
3. I.S. Duff and J.K. Reid, "Algorithm 529: Permutations to Block Triangular Form [F1]," ACM Trans. Mathematical Software, vol. 4, no. 2, 1978, pp. 189–192.
4. J.R. Gilbert, "Predicting Structure in Sparse Matrix Computations," SIAM J. Matrix Analysis and Applications, vol. 15, no. 1, 1994, pp. 62–79.
5. J.R. Gilbert and S.-H. Teng, "MATLAB Mesh Partitioning and Graph Separator Toolbox," 2002; www.cerfacs.fr/algor/Softs/MESHPARTindex.html .
6. J.R. Gilbert, S. Reinhardt, and V.B. Shah, "High Performance Graph Algorithms from Parallel Sparse Matrices," LNCS 4699, B. Kagstrom et al., eds., Springer, 2006, pp. 260–269.
7. V. Shah and J.R. Gilbert, "Sparse Matrices in MATLAB*P: Design and Implementation," LNCS 3296, L. Bouge and V.K. Prasanna, eds., Springer, 2004, pp. 144–155.
8. V.B. Shah, An Interactive System for Combinatorial Scientific Computing with an Emphasis on Programmer Productivity, PhD thesis, Dept. Computer Science, Univ. Calif., Santa Barbara, June 2007.
9. J.R. Gilbert, S. Reinhardt, and V. Shah, "An Interactive Environment to Manipulate Large Graphs," Proc. 2007 IEEE Int'l Conf. Acoustics, Speech, and Signal Processing, IEEE CS Press, 2007, pp. IV-1201–IV-1204.
10. J.R. Gilbert, C. Moler, and R. Schreiber, "Sparse Matrices in MATLAB: Design and Implementation," SIAM J. Matrix Analysis and Applications, vol. 13, no. 1, 1992, pp. 333–356.
11. B. Awerbuch and Y. Shiloach, "New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM," IEEE Trans. Computers, vol. 36, no. 10, 1987, pp. 1258–1263.
12. D. Bader et al., HPCS Scalable Synthetic Compact Applications #2, version 1.1, 2005; www.highproductivity.orgSSCABmks.htm
13. B. McRae, Circuitscape User Manual, v. 2.2, 2006; www.nceas.ucsb.edu/~mcrae/softwarecircuitscape.htm .
14. B.H. McRae, "Isolation by Resistance," Evolution, vol. 60, no. 8, 2006, pp. 1551–1561.
15. R.D. Falgout and U.M. Yang, "Hypre: a Library of High Performance Preconditioners," LNCS 2331, P.M.A. Sloot et al., eds., Springer, 2002, pp. 632–641.
Index Terms:
computing, combinatorics, combinatorial, high-performance computing, HPC, high-level languages, sparse matrix, combinatorics in computing
Citation:
John R. Gilbert, Steve Reinhardt, Viral B. Shah, "A Unified Framework for Numerical and Combinatorial Computing," Computing in Science and Engineering, vol. 10, no. 2, pp. 20-25, Mar./Apr. 2008, doi:10.1109/MCSE.2008.45
