The open archive for STFC research publications

Full Record Details

DOI 10.5286/raltr.2009016
Persistent URL http://purl.org/net/epubs/work/51037
Record Status Checked
Record Id 51037
Title Combinatorial problems in solving linear systems
Abstract Numerical linear algebra anhd combinational optomization are vast subjects; as is their interaction. In virtually all cases there should be a notion of sparsity for a combinatorial problem to arise. Sparse matrices therefore form the basis of the interaction of these seemingly disparate subjects. As the core of many of today's numerical linear algebra computations consists of the solution of sparse linear system by direct or iterative methods, we survey some cominatorial problems, ideas, and algorithms relating to these computations. On the direct methods side, we discuss issues such as matrix ordering; bipartite matching and matrix scaling for better pivoting; task assignment and scheduling for parallel multifrontal solvers. On the iterative side, we discuss the preconditioning techniques including incomplete factorization preconditioners, support graph preconditioners, and algebraic multigrid. In a seperate part, we discuss the block trianglar form of sparse matrices.
Organisation CSE , CSE-NAG , STFC
Keywords combinatorial optimization , Combinatotial scintifc computing , linear system solution , graph theory , sparse matrices
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Technical Reports RAL-TR-2009-016. STFC, 2009. duucRAL2009016.pdf 2009