Permasalahan Kombinatorial dalam Menyelesaikan Sistem Linier

Abstract

Linear system and combinatorial optimization are vast topics. In virtually all cases there should be a notion of sparsity for a combinatorial problem to arise. Sparse matrices form the basis of the interaction of these two seemingly disparate subjects. As the core of many linear algebra computations consists of the solution of sparse linear system by direct or iterative methods. Would survey some com- binatorial problems, ideas and algorithms relating to these computations. On the direct methods side, will discuss issues such as matrix ordering, bipartite matching and matrix scaling for better pivoting, task assignment and scheduling for parallel multifrontal solvers.

Sistem linier dan kombinatorial optimisasi merupakan topik yang luas. Hampir semua kasus terdapat gagasan sparsity untuk masalah kombinatorial yang muncul. Matriks sparse merupakan bentuk dasar dari interaksi kedua subyek yang tampaknya berbeda. Sebagai inti dari banyak perhitungan aljabar linier yang terdiri dari solusi sistem linier sparse dilakukan dengan metode langsung atau metode iteratif. Akan diteliti beberapa masalah kombinatorial, ide-ide dan algoritma yang berkaitan dengan perhitungan. Pada metode langsung, akan didiskusikan tentang matriks ordering (pengalamatan matriks), pencocokan bipartisi dan matriks skala untuk pivoting yang lebih baik, penugasan dan penjadwalan untuk menyelesaikan multifrontal paralel.