Matriks Jarang, Matriks Yang Rata – Rata Elemennya Bernilai 0 – Matriks jarang atau array jarang adalah matriks yang sebagian besar elemen adalah nol. Matriks biasanya disimpan sebagai array dua dimensi. Setiap entri dalam array mewakili elemen ai,j dari matriks dan diakses oleh dua indeks i dan j. Secara konvensional, i adalah indeks baris, diberi nomor dari atas ke bawah, dan j adalah indeks kolom, diberi nomor dari kiri ke kanan. Untuk matriks m × n, jumlah memori yang diperlukan untuk menyimpan matriks dalam format ini sebanding dengan m × n (dengan mengabaikan fakta bahwa dimensi matriks juga perlu disimpan).
Matriks Jarang, Matriks Yang Rata – Rata Elemennya Bernilai 0
transitionmathproject – Dalam kasus matriks sparse, pengurangan kebutuhan memori yang substansial dapat diwujudkan dengan hanya menyimpan entri bukan nol. Bergantung pada jumlah dan distribusi entri bukan nol, struktur data yang berbeda dapat digunakan dan menghasilkan penghematan besar dalam memori bila dibandingkan dengan pendekatan dasar. Trade-off adalah bahwa mengakses elemen individu menjadi lebih kompleks dan struktur tambahan diperlukan untuk dapat memulihkan matriks asli dengan jelas.
Baca Juga : Mengulas Matrix Triangular dan Matriks Tridiagonal
DOK terdiri dari kamus yang memetakan (baris, kolom)-pasangan dengan nilai elemen. Elemen yang hilang dari kamus dianggap nol. Formatnya bagus untuk membangun matriks sparse secara bertahap dalam urutan acak, tetapi buruk untuk mengulangi nilai bukan nol dalam urutan leksikografis. Satu biasanya membangun matriks dalam format ini dan kemudian mengkonversi ke format lain yang lebih efisien untuk diproses. LIL menyimpan satu daftar per baris, dengan setiap entri berisi indeks kolom dan nilainya.
Biasanya, entri ini disimpan diurutkan berdasarkan indeks kolom untuk pencarian yang lebih cepat. Ini adalah format lain yang baik untuk konstruksi matriks inkremental. COO menyimpan daftar tupel (baris, kolom, nilai). Idealnya, entri diurutkan pertama berdasarkan indeks baris dan kemudian berdasarkan indeks kolom, untuk meningkatkan waktu akses acak. Ini adalah format lain yang bagus untuk konstruksi matriks inkremental. Baris terkompresi jarang (CSR) atau penyimpanan baris terkompresi (CRS) atau format Yale mewakili matriks M dengan tiga larik (satu dimensi), yang masing-masing berisi nilai bukan nol, luasan baris, dan indeks kolom.
Ini mirip dengan COO, tetapi memampatkan indeks baris, oleh karena itu namanya. Format ini memungkinkan akses baris cepat dan perkalian matriks-vektor (Mx). Format CSR telah digunakan setidaknya sejak pertengahan 1960-an, dengan deskripsi lengkap pertama muncul pada tahun 1967. Perhatikan bahwa dalam format ini, nilai pertama ROW_INDEX selalu nol dan yang terakhir selalu NNZ, sehingga dalam beberapa hal nilai tersebut berlebihan (walaupun dalam bahasa pemrograman di mana panjang larik perlu disimpan secara eksplisit, NNZ tidak akan menjadi berlebihan). Meskipun demikian, ini menghindari kebutuhan untuk menangani kasus luar biasa saat menghitung panjang setiap baris, karena ini menjamin rumus berfungsi untuk setiap baris i.
Selain itu, biaya memori dari penyimpanan yang berlebihan ini kemungkinan tidak signifikan untuk matriks yang cukup besar. Format matriks jarang Yale (lama dan baru) adalah contoh dari skema CSR. Format Yale lama bekerja persis seperti yang dijelaskan di atas, dengan tiga larik; format baru menggabungkan ROW_INDEX dan COL_INDEX ke dalam satu larik dan menangani diagonal matriks secara terpisah. Ini kemungkinan dikenal sebagai format Yale karena diusulkan dalam laporan Paket Matriks Jarang Yale 1977 dari Departemen Ilmu Komputer di Universitas Yale.
CSC mirip dengan CSR kecuali bahwa nilai dibaca terlebih dahulu oleh kolom, indeks baris disimpan untuk setiap nilai, dan penunjuk kolom disimpan. Misalnya, CSC adalah (val, row_ind, col_ptr), di mana val adalah larik nilai matriks (atas-ke-bawah, lalu kiri-ke-kanan) bukan nol; row_ind adalah indeks baris yang sesuai dengan nilai; dan, col_ptr adalah daftar indeks val di mana setiap kolom dimulai. Nama ini didasarkan pada fakta bahwa informasi indeks kolom dikompresi relatif terhadap format COO. Satu biasanya menggunakan format lain (LIL, DOK, COO) untuk konstruksi. Format ini efisien untuk operasi aritmatika, pengirisan kolom, dan produk matriks-vektor.
Terikat
Jenis matriks sparse khusus yang penting adalah matriks pita, yang didefinisikan sebagai berikut. Bandwidth yang lebih rendah dari matriks A adalah angka terkecil p sedemikian rupa sehingga entri ai,j menghilang setiap kali i > j + p. Demikian pula, bandwidth atas adalah angka terkecil p sehingga ai,j = 0 setiap kali i < j p (Golub & Van Loan 1996, 1.2.1). Sebagai contoh, matriks tridiagonal memiliki bandwidth 1 lebih rendah dan bandwidth atas 1. Sebagai contoh lain, matriks sparse berikut memiliki bandwidth lebih rendah dan atas keduanya sama dengan 3. Perhatikan bahwa nol diwakili dengan titik-titik untuk kejelasan.
Matriks dengan bandwidth atas dan bawah yang cukup kecil dikenal sebagai matriks pita dan sering digunakan untuk algoritma yang lebih sederhana daripada matriks jarang umum; atau seseorang terkadang dapat menerapkan algoritma matriks padat dan mendapatkan efisiensi hanya dengan mengulang sejumlah indeks yang berkurang. Dengan mengatur ulang baris dan kolom matriks A, dimungkinkan untuk mendapatkan matriks A′ dengan bandwidth yang lebih rendah. Sejumlah algoritma dirancang untuk meminimalkan bandwidth. Dalam analisis numerik, matriks dari elemen hingga atau masalah perbedaan hingga sering banded.
Matriks tersebut dapat dilihat sebagai deskripsi dari kopling antara variabel masalah; properti berpita sesuai dengan fakta bahwa variabel tidak digabungkan pada jarak besar yang sewenang-wenang. Matriks tersebut dapat dibagi lebih lanjut – misalnya, matriks berpita ada di mana setiap elemen dalam pita tidak nol. Ini sering muncul ketika diskritisasi masalah satu dimensi. Masalah dalam dimensi yang lebih tinggi juga menyebabkan matriks banded, dalam hal band itu sendiri juga cenderung jarang. Misalnya, persamaan diferensial parsial pada domain persegi (menggunakan perbedaan pusat) akan menghasilkan matriks dengan bandwidth sama dengan akar kuadrat dari dimensi matriks, tetapi di dalam pita hanya 5 diagonal yang bukan nol.
Sayangnya, menerapkan eliminasi Gaussian (atau dekomposisi LU yang setara) ke matriks seperti itu menghasilkan pita yang diisi oleh banyak elemen bukan nol. Dari sudut pandang komputasi, bekerja dengan matriks pita selalu lebih disukai daripada bekerja dengan matriks persegi berdimensi serupa. Matriks pita dapat disamakan dalam kompleksitasnya dengan matriks persegi panjang yang dimensi barisnya sama dengan bandwidth matriks pita. Dengan demikian pekerjaan yang terlibat dalam melakukan operasi seperti perkalian turun secara signifikan, sering menyebabkan penghematan besar dalam hal waktu perhitungan dan kompleksitas.
Karena matriks jarang memberikan perhitungan yang lebih efisien daripada matriks padat, serta dalam pemanfaatan penyimpanan komputer yang lebih efisien, ada banyak penelitian yang berfokus pada menemukan cara untuk meminimalkan bandwidth (atau secara langsung meminimalkan pengisian) dengan menerapkan permutasi ke matriks, atau transformasi kesetaraan atau kesamaan lainnya. Algoritma Cuthill-McKee dapat digunakan untuk mengurangi bandwidth dari matriks simetris jarang. Namun, ada matriks yang kinerja algoritma Cuthill-McKee terbalik lebih baik. Ada banyak metode lain yang digunakan. Masalah menemukan representasi matriks dengan bandwidth minimal melalui permutasi baris dan kolom adalah NP-hard.