Multifrontal solution of sparse problems

by Oleg Shcherbina and Arnold Neumaier

University of Vienna

Most large-scale problems have a sparse structure described by a (sometimes very large) graph. In generalization of the multifrontal approach to solving sparse linear systems of equations, one may solve many other classes of large-scale problems by means of a so-called tree decomposition of their associated graph. A tree decomposition gives rise to a covering of the edges of the graph by a small sets of fronts whose intersection structure is described by a so-called join tree. The join tree structure enables many otherwise NP-hard problems to be solved in time proportional to the number of fronts, provided that the associated subproblems on each front can be solved in constant time.

This page is a collection of links to papers and web sites on material related to multifrontal techniques. (Pointers to additional work are appreciated.) It contains sections on

Graphs and trees

A. Berry, J.-P. Bordat, and O. Cogis, Generating all the minimal separators of a graph , Int. J. Found. Comput. Sci., 11 (2000), 397-403.

Chordal Graph Page

S. Friedland, On the graph isomorphism problem, Manuscript (2008).

R.E. Tarjan and M. Yannakakis, Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs , SIAM J. Computing 13 (1984), 566-579.

J. Tor\'an, Reductions to Graph Isomorphism , pp. 158--167 in: Lecture Notes in Computer Science, Vol. 4855, Springer, Berlin 2007.

Join trees

R. Dechter, Y. El Fattah, Topological parameters for time-space tradeoff, Artif. Intell. 125 (2001), 93-118.

R. Dechter, J. Pearl, Tree clustering for constraint networks, Artif. Intell. 38 (1989), 353-366.

Multifrontal algorithms

J.W.H. Liu, The multifrontal method for sparse matrix solution: theory and practice, SIAM Review 34 (1992), 82-109.

Graph partitions and their join trees

C.J. Alpert, S.Z. Yao, Spectral partitioning: the more eigenvectors, the better. In: 32th DAC, ACM/IEEE, 195-200 (1995).

E.G. Boman, D. Bozdag, U.V. Catalyurek, K.D. Devine, A.H. Gebremedhin, P.D. Hovland, A. Pothen, and M.M. Strout, Enabling high performance computational science through combinatorial algorithms, Proceedings of SciDAC 2007, Journal of Physics: Conference Series 78 (2007) 012058, August 2007.

J. Falkner, F. Rendl, H. Wolkowicz, A computational study of graph partitioning, Math. Programming 66 (1994), 211-239.

C.M. Fiduccia, R.M. Mattheyses, A linear-time heuristics for improving network partitions. pp. 175-181 in: Proc. 19th ACM/IEEE Design Automation Conference, (1982).

G.W. Flake, R.E. Tarjan, K. Tsioutsiouliklis, Graph clustering and minimum cut trees, Internet Mathematics 1 (2003), 385-408.

A. Gebremedhin, F. Manne, A. Pothen, What color is your Jacobian? Graph coloring for computing derivatives, SIAM Review 47 (2005), 629-705.

A. Gebremedhin, A. Tarafdar, F. Manne, A. Pothen, New acyclic and star coloring algorithms with application to computing Hessians, SIAM J. Sci. Comput. 29 (2007), 1042-1072

R.E. Gomory, T.C. Hu, Multi-terminal network flows, SIAM J. on Applied Mathematics 9 (1961), 551-570.

A. Gupta, Fast and effective algorithms for graph partitioning and sparse matrix ordering, IBM J. Res. Development 41 (1997), 171-184.

B. Hendrickson and A. Pothen, Combinatorial Scientific Computing: The enabling power of discrete algorithms in computational science, Proceedings of the 7th International Meeting on High Performance Computing for Computational Science (VECPAR'06), Lecture Notes in Computer Science, Springer Verlag, 21 pp., 2006.

B. Hendrickson, R. Leland, A multilevel algorithm for partitioning graphs, In: Proc. Supercomputing '95, ACM, San-Diego, 1995.

Hypertree Decomposition.

JOSTLE -- graph partitioning software.

G. Karypis, V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs. Tech. Rep. TR95-035. University of Minnesota, Minneapolis, 1995.

G. Karypis, V. Kumar, MeTiS -- a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. Version 4, University of Minnesota, 1998.

PARTY partitioning library.

R. Preis and R. Diekmann, Party -- a software library for graph partitioning, In: B.H.V. Topping (ed.) Advances in Computational Mechanics with Parallel and Distributed Processing, pp.63-71, 1997.

H.D. Simon, Partitioning of unstructured problems for parallel processing, Computing Systems in Engineering 2 (1991), 135-148.

Hypergraph partitioning and hypergraph decompositions

Hypertree Decompositions

A. Dermaku, T. Ganzow, G. Gottlob, B. McMahan, N. Musliu, M. Samer, Heuristic methods for hypertree decompositions. DBAI Techn. Report DBAI-TR-2005-53. Technische Universitaet Wien, Vienna (2005).

G. Gottlob, N. Leone, F. Scarcello, A comparison of structural CSP decomposition methods, Artificial Intelligence 124 (2000), 243-282.

G. Gottlob, N. Leone, F. Scarcello, Hypertree decompositions: A survey, pp. 37-57 in: Mathematical foundations of computer science. 26th international symposium, MFCS 2001. Proceedings. Springer, Berlin, Lect. Notes Comput. Sci. 2136, 2001.

G. Gottlob, M. Grohe, N. Musliu, M. Samer and F. Scarcello, Hypertree Decompositions: Structure, Algorithms, and Applications,Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05), Lecture Notes in Computer Science , pp.1-15, 2005.

G. Karypis, R. Aggarwal, V. Kumar, S. Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Trans. Very Large Scale Integr. Syst. 7 (1999), 69-79.

PaToH Partitioning Tools for Hypergraph.

M. Samer, Hypertree decomposition via branch-decomposition, pp. 1535-1536 in: International Joint conference of Artificial Intelligence (IJCAI05), 2005.

Elimination Game and Vertex Elimination

K. Grant and M.C. Horsch, Methods for Constructing Balanced Elimination Trees and Other Recursive Decompositions, Manuscript (2005).

E. Loute, Gaussian elimination as a computational paradigm. Core discussion paper 2003/59.

A. Natanzon, R. Shamir and R. Sharan, A polynomial approximation algorithm for the minimum fill-in problem, pp. 41-47 in: Proc. 30th Ann. ACM Symp. on Theory of Comp., ACM 1998.

S. Parter, The use of linear graphs in Gauss elimination, SIAM Review 3 (1961), 119-130.

D. Rose, R. Tarjan, G. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM Journal on Computing 5 (1976), 266-283.

M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Alg. Discr. Meth. 2 (1981), 77-79.

Minimum degree algorithms and nested dissection

P.R. Amestoy, T.A. Davis, I.S. Duff, An approximate minimum degree ordering algorithm. SIAM J Matrix Anal. Appl. 17 (1996), 886-905.

C. Ashcraft, Compressed graphs and the minimum degree algorithm, SIAM J. Sci. Comput. 16 (1995), 1404-1411.

C. Ashcraft, J.W.H. Liu, Robust ordering of sparse matrices using multisection, SIAM J. Matrix Anal. Appl. 19 (1998), 816-832.

T.A. Davis, P. Amestoy and I.S. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. Appl. 17 (1996), 886-905.

P. Heggernes, S.C. Eisenstat, G. Kumfert, A. Pothen, The Computational Complexity of the Minimum Degree Algorithm. Techn. report UCRL-ID-148375. Lawrence Livermore National Laboratory (2001).

A. George and J.W.H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Rev. 31 (1989),pp. 1-19.

A. George, J.W. Poole, and R.Voigt, Incomplete nested dissection for solving $n$ by $n$ grid problems, SIAM J. Numer. Anal. 15 (1978), 663-673.

A. George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10 (1973), pp. 345-363.

A. George and J.W.H. Liu, A fast implementation of the minimum degree algorithm using quotient graphs, ACM Trans. Math. Software 6 (1980), 337-358.

B. Hendrickson, E. Rothberg, Improving the run time and quality of nested dissection ordering, SIAM J. Sci. Comput. 20 (1998), 468--489.

S.I. Larimore, An approximate minimum degree column ordering algorithm, MS Thesis, Dept. of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 1998.

R.J. Lipton, D.J. Rose, R.E. Tarjan, Generalized nested dissection, SIAM J. of Numerical Analysis 16(2) (1979), 346-358.

J.W.H. Liu, The minimum degree ordering with constraints, SIAM J. Sci. Comput. 10 (1989), pp. 1136-1145.

F. Pellegrini, J. Roman, P. Amestoy, Hybridizing nested dissection and halo approximate degree for efficient sparse matrix ordering, Lecture Notes in Computer Science 1586, Springer, Berlin 1999, pp. 986-995.

F. Pellegrini, J. Roman, and P. R. Amestoy. Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering. Concurrency: Practice and Experience, 12:69-84, 2000.

Constructing tree decompositions

E. Amir, Efficient approximation for triangulation of minimum treewidth. Uncertainty in Artificial Intelligence (2001), 7-15.

S. Arnborg, D.G. Corneil and A. Proskurowski, Complexity of finding embeddings in a $k$-tree, SIAM J. Alg. Discr. Meth. 8 (1987), 277-284.

S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial $k$-trees, Discrete Applied Mathematics 23 (1989), 11-24.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, J. of Alg. 12 (1991), 308-340.

S. Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded decomposability -- a survey, BIT Numerical Mathematics 25 (1985), 1-23.

S. Arnborg and A. Proskurowski, Characterization and Recognition of Partial k-trees, SIAM J. Alg. Discr. Meth. 7 (1986), 305-314.

E.H. Bachoore and H.L. Bodlaender, New Upper Bound Heuristics for Treewidth, pp. 216-227 in: Lecture notes in computer science , Vol. 3503, Springer, Berlin 2005.

A. Becker, D. Geiger, A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence 125 (2001), 3-17.

A. Becker and D. Geiger, A sufficiently fast algorithm for finding close to optimal junction trees, pp. 81-89 in: Uncertainty in AI (UAI'96), 1996.

A. Berry, A wide-range efficient algorithm for minimal triangulation. In: Proceedings of SODA, (1999).

J.R.S. Blair and B.W. Peyton, An introduction to chordal graphs and clique trees. In: Graph theory and sparse matrix computation. 1-29. Springer, New York (1993).

J.R.S. Blair and B.W. Peyton, On Finding Minimum-Diameter Clique Trees, Nordic J. Computing, 1 (1994), 173-201.

H.L. Bodlaender, Treewidth: Algorithmic techniques and results, pp. 19-36 in: Privara L et al.(eds) Mathematical foundations of computer science. 22nd international symposium, MFCS '97, Bratislava, Slovakia, August 25-29, 1997. Proceedings. Lect. Notes Comput. Sci. 1295. Springer, Berlin (1997)

H.L. Bodlaender, Discovering Treewidth, pp. 1-16 in: Proceedings of SOFSEM Springer-Verlag, LNCS 3381. 2006.

H. Bodlaender, A.M.C.A. Koster, Combinatorial optimization on graphs of bounded treewidth, Computer Journal 51 (2008), 255-269.

H. Bodlaender, A.M.C.A. Koster, F. van den Eijkhof, and L.C. van der Gaag, Pre-processing for Triangulation of Probabilistic Networks, pp. 32-39 in: Proc. 17th Conf. Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2001.

H.L. Bodlaender, Treewidth: Characterizations, Applications, and Computations, technical report UU-CS-2006-041,Department of Information and Computing Sciences, Utrecht University.

V. Bouchitt\'e, D. Kratsch, H. Muller, I. Todinca, On treewidth approximations, Discrete Appl. Math. 136 (2004), 183-196.

A. Cano and S. Moral, Heuristic Algorithms for the Triangulation of Graphs, pp. 98-107 in: Lecture Notes In Computer Science; Vol. 945, Springer 1994.

W. Cook, P.D. Seymour, Tour merging via branch-decomposition, INFORMS Journal on Computing 15 (2003),233-248.

P.A. Dow and R.E. Korf, Best-first search for treewidth, Proc. 22nd Conf. Artificial Intelligence (AAAI-2007), Vancouver, British Columbia, July 2007.

F. Fomin, D. Kratsch, I. Todinca, Exact (exponential) algorithms for treewidth and minimum fill-in, pp. 568-580 in: Proceedings of ICALP, (2004).

V. Gogate, R. Dechter, A complete anytime algorithm for treewidth. In: Proceedings of UAI (2004), 201-208.

P. Heggernes, Minimal triangulations of graphs: A survey, Discrete Mathematics 306 (2006), 297-317.

I.V. Hicks, A.M.C.A. Koster, E. Kolotoglu, Branch and Tree Decomposition Techniques for Discrete Optimization. In: Tutorials in Operations Research. New Orleans: INFORMS, 2005, 129.

K. Kask, R. Dechter, J. Larrosa, A. Dechter, Unifying cluster-tree decompositions for reasoning in graphical models, Artif. Intell. 160 (2005), 165-193.

U. Kjaerulff, Triangulation of graphs - algorithms giving small total state space, Tech. Report, Aalborg, Denmark, 1990.

A.M.C.A. Koster, C.P.M. van Hoesel, A.W.J. Kolen, Solving frequency assignment problems via tree-decomposition. In: Broersma, H.J. et al.(eds.). 6th Twente workshop on graphs and combinatorial optimization. Univ. of Twente, Enschede, Netherlands, May 26-28, 1999.

A.M. Koster, H L. Bodlaender, and S.P.M. van Hoesel, Treewidth: computational experiments. Techn. Report 01-38, Berlin, Germany, 2001.

O.A. Shcherbina, Tree decomposition and discrete optimization problems: a survey, Cybernetics and system analysis 43 (2007), 549-562.

K. Shoikhet, D. Geiger, A practical algorithm for finding optimal triangulation, pp. 185-190 in: Proceedings of AAAI (1997).

T. Wolle, Computational aspects of Treewidth, lower bounds and networks reliability. Dissertation: UU Universiteit Utrecht (2005).

Software packages for tree decomposition



TreeD Library


Sparse linear algebra

Y.E. Campbell, T.A. Davis, Computing the sparse inverse subset an inverse multifrontal approach, Technical Report TR-95-021, Computer and Information Sciences Department, University of Florida, Gainesville, October, 1995.

IAIN S. DUFF. A Survey of Sparse Matrix Research, PROCEEDINGS OF THE IEEE, VOL. 65 , N 4, 1977, p. 500-535.

A.M. Erisman, W. F. Tinney, On computing certain elements of the inverse of a sparse matrix, Comm. ACM 18 (1975), 177-179.

M. Fukuda, M. Kojima, K. Murota, and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: general framework, SIAM J. Optimization 11 (2000), 647-674.

A. George and J.W.H. Liu, Algorithms for matrix partitioning and the numerical solution of finite element systems, SIAM J. Numer. Anal. 15 (1978), 293-327. P> A. George and J.W.H. Liu, A quotient graph model for symmetric factorization, In: I.S.Duff and G.W.Stewart (eds.), Sparse Matrix Proceedings, SIAM Publications, 1978, 154-175.

N.I.M. Gould, J.A. Scott, and Y. Hu, A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM Trans. Math. Software 33 (2007), No. 10, B1-B32.

R. Grone, C.R. Johnson, E.M. S\'a, and H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra and Appl., 58 (1984), 109-124.

A. Gupta, G. Karypis and V. Kumar, Highly scalable parallel algorithms for sparse matrix ordering, IEEE Transactions on Parallel and Distributed Systems, 1994.

B. Hendrickson, R. Leland, The Chaco user's guide. Version 2.0. Technical Report SAND95-2344, Sandia National Laboratories, 1995.

J.W.H. Liu, E.G. Ng, and B.W. Peyton, On finding supernodes for sparse matrix computations, SIAM J. Matrix Anal. Appl. 14 (1993), 242-252.

J.W.H. Liu, Equivalent sparse matrix reordering by elimination tree rotations, SIAM J. Sci. Comput. 9 (1988), 424-444.

J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl. 11 (1990), 134-172.

K. Nakata, K. Fujitsawa, M. Fukuda, M. Kojima, and K. Murota, Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical details, Mathematical Programming Series B, 95 (2003), 303-327.

H. Niessner, K. Reichert, On computing the inverse of a sparse matrix, International Journal for Numerical Methods in Engineering 19 (1983), 1513-1526.

F. Pellegrini, J. Roman, Sparse matrix ordering with SCOTCH. In: Proc. of HPCN'97, Vienna, LNCS 1225, 370-378 (1997).

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

SPOOLES 2.2 : SParse Object Oriented Linear Equations Solver

M.M. Strout, L. Carter, J. Ferrante, J. Freeman, B. Kreaseck, Combining performance aspects of irregular Gauss-Seidel via sparse tiling, In: Proc. of the 15th Workshop on Languages and Compilers for Parallel Computing, College Park MD 2002.

S. Vavasis, A note on efficient computation of the gradient in semidefinite programming.

Nonserial dynamic programming

R. Dechter, Bucket Elimination: a Unifying Framework for Reasoning, Artificial Intelligence 113 (1999), 41-85.

R. Giegerich and C. Meyer, Algebraic dynamic programming , In H. Kirchner and C. Ringeissen, eds, Algebraic Methodology And Software Technology, pages 349-364. LNCS 2422, 2002, Springer-Verlag

J. Hooker, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction, Wiley, New York 2000.

J.N. Hooker, Logic, optimization and constraint programming, INFORMS Journal on Computing 14 (2002), 295-321.

L. Huang, Dynamic programming algorithms in semiring and hypergraph frameworks

L. Huang, D. Chiang, Better $k$-best parsing, Proc. 9th Int. Workshop Parsing Technologies (IWPT), pp. 53-64, Vancouver, October 2005.

M. Pouly and J. Kohlas, Dynamic Programming \& Local Computation, Manuscript (2007)

A. Rosenthal, Dynamic programming is optimal for nonserial optimization problems, SIAM J. Comput. 11 (1982), 47-59.

O.A. Shcherbina, Local elimination algorithms for solving sparse discrete problems, Computational Mathematics and Mathematical Physics 48 (2008), 152-167.

P.P. Shenoy, Valuation-based systems for Bayesian decision analysis, Operations Research 40 (1992), 463-484.

P.P. Shenoy, Axioms for Dynamic Programming, pp. 259-275 in: Computational Learning and Probabilistic Reasoning (A. Gammerman, ed.), Wiley, Chichester 1996.

Multifrontal algorithm for querying data bases

C. Beeri, R. Fagin, D. Maier, and M. Yannakakis, On the desirability of acyclic database schemes, J. ACM 30 (1983), 479-513.

M. Gyssens, P.G. Jeavons, D.A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artif. Intell. 66 (1994), 57-89.

P.A. Bernstein and N. Goodman, Powers of natural semijoins, SIAM J. Comput. 10 (1981), 751-771.

M. Yannakakis, Algorithms for acyclic database schemes, pp. 82-94 in: C. Zaniolo, C. Delobel (Eds.), Proc. Internat. Conference on Very Large Data Bases (VLDB-81), Cannes, France, 1981.

Probabilistic applications of multifrontal approach

R.G. Almond, Graphical Belief Modeling, Chapman and Hall, London 1995.

I. Arad, Z. Landau, Quantum computation and the evaluation of tensor networks, arXiv:0805.0040 (May 2008).

O. Banerjee, A. d'Aspremont, L. El Ghaoui, Sparse covariance selection via robust maximum likelihood estimation, arXiv:cs/0506023v1

O. Banerjee, L.E. Ghaoui, A. d'Aspremont, and G. Natsoulis, Convex optimization techniques for fitting sparse Gaussian graphical models, In: Proceedings of the 23rd international Conference on Machine Learning (Pittsburgh, Pennsylvania, June 25-29, 2006). ICML '06, vol. 148 (2006). ACM, New York, NY, 89-96.

T. Berger and Z. Ye, Entropic aspects of random fields on trees, IEEE Trans. Information Theory 36 (1990), 1006-1018.

M. Van den Nest, W. Duer, G. Vidal, and H.J. Briegel, Classical simulation versus universality in measurement-based quantum computation, Physical Review A 75 (2007), 012337: 1-15.

L. Cincio, J. Dziarmaga, and M.M. Rams, Multiscale Entanglement Renormalization Ansatz in Two Dimensions: Quantum Ising Model, Phys. Rev. Lett. 100, 240603 (2008).

R. Dahlhaus, Graphical interaction models for multivariate time series, Metrika, 51 (2000), 157-172.

J. Dahl, L. Vandenberghe, V. Roychowdhury, Covariance selection for non-chordal graphs via chordal embedding, Optimization Methods and Software (2008) (to appear).

M. Drton, M.D. Perlman, A SINful approach to Gaussian graphical model selection, Journal of Statistical Planning and Inference 138 (2008), 1179-1200.

W.J. Ewens and N.C.E. Shute, A resolution of the ascertainment sampling problem. I. Theory. Theor Popul Biol 30 (1986), 388-412

M.J. Flores, Bayesian networks inference: Advanced algorithms for triangulation and partial abduction, Ph.D. Thesis, University de Castilla - La Mancha (2005).

HUGIN API Reference Manual, Version 6.7, Manuscript (2007).

J.K. Johnson, V. Chandrasekaran, and A.S. Willsky, Learning Markov structure by maximum entropy relaxation, 11th Inter. Conf. on AI and Stat. (AISTATS '07), San Juan, Puerto Rico, March 2007.

R. Jozsa, On the simulation of quantum circuits, arXiv:quant-ph/0603163v1

S.L. Lauritzen and D.J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems, J. Roy. Stat. Soc. B 50 (1988), 205-247.

V. Lepar and P.P. Shenoy, A comparison of architectures for exact computation of marginals, Tech. Rep. 1997.

Z. Lu, Smooth optimization approach for covariance selection, SIAM J. Optimization, to appear.

I.L. Markov, Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM J. Comput. 38 (2008), 963-981.

J. Moussouris, Gibbs and Markov random systems with constraints, J. Stat. Phys. 10 (1974), 11-33.

A. Neumaier, E. Groeneveld, Restricted maximum likelihood estimation of covariances in sparse linear models, Genet. Sel. Evol. 30 (1998), 3-26.

A. Neumann, Statistical shape description using decomposable graphical models, in: University of the Federal Armed Forces Hamburg, Discussion Papers in Statistics and Quantitative Economics, No. 84, 1998.

D. Nilsson, An efficient algorithm for finding the $M$ most probable configurations in Bayesian networks, Statistics and Computing 8 (1998), 159-173.

D. Nilsson, J. Goldberger, Sequentially finding the $N$-best list in hidden Markov models, International Conference on Artificial Intelligence (IJCAI), 2001.

J. Pearl, Reverend Bayes on inference engines: A distributed hierarchical approach, pp. 133-136 in: D.L. Waltz (ed.), Proc. National Conf. Artificial Intelligence, AAAI Press, Menlo Park 1982.

J. Pearl, A constraint-propagation approach to probabilistic reasoning, pp. 357-370 in: L.N. Kanal and J.F. Lemmer (eds.), Uncertainty in Artificial Intelligence, North Holland, Amsterdam 1986.

J. Pearl, Graphical models, causality, and intervention, Statistical Science 8 (1993), 266-269.

A. Pelizzola, Cluster variation method in statistical physics and probabilistic graphical models, J. Phys. A: Math. Gen., 38 (2005), R309-R339.

Z. Rakamaric, C. Dabrowski, CS 532c - Probabilistic Graphical Models $N$-Best Hypotheses

A. Roverato, Prior distributions for Gaussian graphical models: a comparison between the directed and undirected case, Metron, 59 (2001), 205-216.

H. Rue, S. Martino, Approximate Inference for Hierarchical Gaussian Markov Random Fields Models, Preprint Statistics No. 7/2005 Norwegian University of Science and Technology, Trondheim, Norway, 2005.

H. Rue, S. Martino, Approximate Bayesian inference for hierarchical Gaussian Markov random field models, Journal of Statistical Planning and Inference 137 (2007) 3177 - 3192.

H. Rue, S. Martino, N. Chopin, Approximate Bayesian Inference for Latent Gaussian Models Using Integrated Nested Laplace Approximations, Technical report No. 1/2007, Department of Mathematical Sciences, Norwegian University of Science and Technology.

L.K. Saul and M.I. Jordan, Learning in Boltzmann trees, Neural Comput. 6 (1994), 1173-1183.

C. Schneuwly, M. Pouly, and J. Kohlas, Local Computation in Covering Join Trees. Tech. rept. 04-16. Department of Informatics, University of Fribourg (2004).

G. Shafer and P.P. Shenoy, Local computations in hypertrees, Manuscript of a book (1991).

O.A. Shcherbina, Tree decomposition and postoptimality analysis in discrete optimization (2009), arXiv:0903.4435v1 [cs.DM]

Y.-Y. Shi, L.-M. Duan, G. Vidal, Classical simulation of quantum many-body systems with a tree tensor network, Phys. Rev. A 74, 022320 (2006), quant-ph/0511070.

G. Vidal, A class of quantum many-body states that can be efficiently simulated, arXiv:quant-ph/0610099

G. Vidal, Entanglement Renormalization, Phys. Rev. Lett. 99, 220405 (2007), cond-mat/0512165

N. Wermuth, Linear recursive equations, covariance selection, and path analysis, Journal of the American Statistical Association, 75(372) (1980), 963-972.

Constraint Satisfaction and Discrete Optimization Problems

S. Bistarelli, U. Montanari, and F. Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM, 44 (1997), 201-236.

H. Chen, Quantified constraint satisfaction and bounded treewidth, in: Proceedings of ECAI-04, 2004, pp. 161-165.

R. Dechter , and J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence 34 (1987), 1-38.

R. Dechter, Tractable Structures for Constraint satisfaction problems

E.C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM) 29 (1982), 24-32.

A.Y. Grama, V. Kumar, A survey of parallel search algorithms for discrete optimization problems, ORSA Journal of Computing, 7(4)(1995), 365-85.

J. Gu, P.W. Purdom, J. Franco, B.W. Wah, Algorithms for the satisfiability (SAT) problem: A survey. pp. 19-153 in: Satisfiability Problem Theory and Applications, 1997.

P.G. Jeavons, M. Gyssens, D.A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artif. Intell., 66 (1994), 57-89.

P. J\'egou, S.N. Ndiaye, C. Terrioux, Computing and exploiting tree-decompositions for (Max-)CSP. In: Proc. 11th Int. Conf. Principles Practice Constraint Programming (CP-2005), 777-781 (2005).

J. Pearson, P. Jeavons, A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway University of London, 1997.

E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.

Finding the K Shortest Hyperpaths

L.R. Nielsen, K.A. Andersen, D. Pretolani, Finding the $K$ Shortest Hyperpaths, Computers and Operations Research 32 (2005), 1477-1497.

L.R. Nielsen, D. Pretolani, K.A. Andersen, Finding the $K$ shortest hyperpaths using reoptimization, Operations Research Letters 34 (2006), 155-164.


Charles J. Alpert

Patrick R. Amestoy

Anne Berry

Hans L. Bodlaender

Bruno Courcelle

Tim Davis

Rina Dechter

Florin Dobrian

Augustine Esogbue

Miroslav Fiedler

Alan D. George

Georg Gottlob

Martin Grohe

Pinar Heggernes

Uffe Kjaerulff

Arie Koster

Steffen Lauritzen

Judea Pearl

Alex Pothen

Andrzej Proskurowski

Neil Robertson

Donald Rose

Alberto Roverato

Havard Rue

Detlef Seese

Paul Seymour

Prakash P. Shenoy

Horst D. Simon

Robert E. Tarjan

Robin Thomas

Elizabeth A. Thompson

Prof. Edward Tsang

Jeffrey D. Ullman

Mihalis Yannakakis

References without Web-links

W.W. Barrett, C.R. Johnson, and M. Lundquist, Determinantal formulation for matrix completions associated with chordal graphs, Linear Algebra and Appl., 121 (1989), 265-289.

U. Bertel\'e and F. Brioschi, Nonserial Dynamic Programming, Academic Press, New York 1972.

T. Bui, C. Jones, A heuristic for reducing fill in sparse matrix factorization. In: Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing. SIAM, Philadelphia, 1993, 445-452.

L.M. de Campos, J.A. G\'amez , S. Moral, Partial abductive inference in bayesian networks by using probability trees, Int. J. Approx. Reasoning 27 (2001), 263-283.

C. Cannings, E.A. Thompson and M.H. Skolnick, Probability functions on complex pedigrees. Adv. Appl. Prob. 10 (1978), 26-61.

B. Courcelle, The monadic second-order logic of graphs I: Recognizable sets of finite graphs, Information and Computation 85 (1990), 12-75.

B. Courcelle, Graph rewriting: An algebraic and logic approach. pp. 194--242 in: van Leeuwen, J. (ed). Handbook of Theoretical Computer Science, Elsevier, 1990.

R.G. Cowell, A.P. Dawid, S.L. Lauritzen, and D.J. Spiegelhalter, Probabilistic Networks and Expert Systems, Springer 1999.

Y. Crama, P. Hansen, and B. Jaumard, The basic algorithm for pseudo-boolean programming revisited, Discrete Applied Mathematics 29 (1990), 171-185.

R. Dechter, Constraint processing. Morgan Kaufmann, 2003.

R. Dechter, A. Dechter, and J. Pearl, Optimization in constraint networks, pp. 411-425 in: Influence Diagrams, Belief Nets and Decision Analysis, Wiley, New York 1990.

F. Dobrian, External memory algorithms for factoring sparse matrices, PhD Thesis, Old Dominion University, Dec. 2001.

I.S. Duff, A.M. Erisman and J.K. Reid, Direct Methods for Sparse Matrices. Clarendon Press, Oxford 1986.

A.O. Esogbue, B. Marks, Non-serial dynamic programming - A survey, Operational Research Quarterly 25 (l974), 253-265.

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

M.J. Flores, J.A. Gamez, S. Moral, Abductive Inference in Bayesian Networks: Finding a Partition of the Explanation Space, In: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Springer, Berlin, Heidelberg, Volume 3571/2005, 63-75.

M.J. Flores and J.A. G\'amez, Triangulation of Bayesian networks by retriangulation, Int. J. Intelligent Systems 18 (2003), 153-164.

M.J. Flores and J.A. Gamez, A Review on Distinct Methods and Approaches to Perform Triangulation for Bayesian Networks, pp. 127-152 in: Advances in Probabilistic Graphical Models, Studies in Fuzziness and Soft Computing, Vol. 214, Springer 2007.

D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965), 835-855.

A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems. Englewood Cliffs: Prentice-Hall Inc., 1981.

M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Acad. Press, London 1980.

J.M. Hammersley and P.E. Clifford, Markov fields on finite graphs and lattices, Unpublished manuscript (1971).

C.-W. Ho and R.C.T. Lee, Counting clique trees and computing perfect elimination schemes in parallel, Infor. Process. Lett. 31 (1989), 61-68.

F.V. Jensen, Bayesian Networks and Decision Graphs, Springer, 2002.

B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Techn. Journal 49 (1970), 291-307.

E.S. Kirsch and J.R.S. Blair, Practical parallel algorithms for chordal graphs, pp. 372--382 in: Proc. Int. Conf. Computing Information (ICCI '91), Advances in Computing and Information, Ottawa, Canada, May 1991.

S.L. Lauritzen, Graphical models, Clarendon Press, Oxford 1996.

J.W.H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Software 11 (1985), 141-153.

A. Martelli, U. Montanari, Nonserial dynamic programming: on the optimal strategy of variable elimination for the rectangular lattice, J. Math. Anal. Appl. 4O (1972), 226-242.

L.G. Mitten, Composition principles for the synthesis of optimal multi-stage processes, Oper. Res. 12 (1964), 610-619.

R.E. Neapolitan, Probabilistic Reasoning in Expert Systems, Wiley, New York 1990.

J. Pearl, Probabilistic reasoning in intelligent systems, Morgan Kaufmann, San Mateo, CA, 1988.

J. Pearl, Causality: Models, Reasoning, and Inference, Cambridge Univ. Press, Cambridge 2001.

J. Pearl, Distributed revision of composite beliefs, Artificial Intelligence 33 (1987), 173-215.

N. Robertson, P.D. Seymour, Graph minors. II. Algorithmic aspects of tree width, J. Algorithms 7 (1986), 309-322.

D.J. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read R.C. (ed.) Graph Theory and Computing, pp. 183-217. Academic Press, New York, 1972.

E. Rothberg, Robust ordering of sparse matrices: A minimum degree, nested dissection hybrid. Sylicon Graphics, Manuscript, 1995.

P. Seidel, A new method for solving constraint satisfaction problems. In: Proc. of the 7th IJCAI, 338-342. Vancouver, Canada (1981).

O.A. Shcherbina, On local algorithms of solving discrete optimization problems, Problems of Cybernetics (Moscow) 40 (1983), pp. 171-200.

O.A. Shcherbina, Postoptimal analysis in nonserial dynamic programming. In: Proceedings of Second International Conference MCO 2008 ''Modelling, Computation and Optimization in Information Systems and Management Sciences'', Metz, France Luxembourg, September 8-10, 2008. Communications in Computer and Information Science 14:308-317. Springer, Berlin/Heidelberg (2008)

O.A. Shcherbina, Graph-Based Local Elimination Algorithms in Discrete Optimization. In: Foundations of Computational Intelligence Volume 3. Global Optimization Series: Studies in Computational Intelligence , Vol. 203 / Abraham A, Hassanien A-E, Siarry P, Engelbrecht A (Eds). Springer Berlin / Heidelberg. (2009) P. 235-266.

K. Takahashi, J. Fagan, and M.-S. Chin, Formation of a sparse bus impedence matrix and its application to short circuit study, 8th PICA Conf. Proc., June 4-6, 1973, Minneapolis, Minn. R.E. Tarjan, Graph theory and Gaussian elimination, pp. 3--22 in: J.R. Bunch and D.J. Rose (eds.), Sparse Matrix Computations, Academic Press, New York 1976.

W.F. Tinney, J.W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, J. Proc. IEEE, 55 (1967), 1801-1809.

J. Ullman, Principles of Database and Knowledge-Base Systems, 2 Volumes. Computer Science Press, New York 1988/89.

J. Whittaker, Graphical Models in Applied Multivariate Statistics, Wiley, New York (1990)

Some of My Other Pages

Mathematical Software
Statistics Links
Computational Mathematics Links
Mathematics Links
FMathL - Formal mathematical language
Global Optimization
my home page (

Arnold Neumaier (