A recursive graph bipartitioning algorithm by vertex separators with fixed vertices for permuting sparse matrices into block diagonal form with overlap

Seyrek doğrusal denklem sistemlerinin ön hazırlık kullanılarak cözümü çizge bölümleme araçları kullanılarak etkili ve verimli bir biçimde koşut hesaplamasına uygun hale getirilebilir. Bu tez çalışmasında, çarpımsal schwarz ön hazırlayıcısının koşut hesaplanmasında kullanılmak üzere bir seyrek matrisin örtüşen blok köşegen biçimine yeniden düzenlenmesi problemi incelenmektedir. Ardışık köşegen blokları örtüşen blok köşegen matrislere örtüşen blok köşegen matrisler denir. Bu yeniden düzenleme probleminin çizge kuramı kullanılarak ifade edilebilmesi için Düğüm Ayıracı ile Çizge Bölümleme (DAÇB) probleminin kısıtlı bir çeşidi olan sıralı DAÇB (sDAÇB) problemi tanıtılmaktadır. sDAÇB probleminde amaç iki ardışık düğüm bölümünün sadece bir düğüm ayıracı ile bağlanabildiği sıralı bir düğüm bölümlemesi bulmaktır.Varolan çizge bölümleme araçları sDAÇB problemini çözememektedirler. Bu nedenle, bu tez çalışmasında, düğüm ayıraçlarını ve yeni bir düğüm sabitleme düzenini kullanan özyineli bir çizge bölümleme algoritması önerilmektedir. Bu algoritma ile sabit düğümleri destekleyen bir DAÇB aracı etkili ve verimli bir şekilde kullanılabilmektedir. Ayrıca, bir sDAÇB çözümünün uygulanabilirliği için yeterli ve gerekli koşul incelenerek önerilen yaklaşım kuramsal olarak doğrulanmıştır. Çeşitli matrisler üzerinde yapılan deneylerin sonuçları önerilen yaklaşımın geçerliliğini doğrulamaktadır.