Wikipedia

Matriks rongga: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
k Menambah Kategori:Matematika menggunakan HotCat
R.A Aziz H (bicara | kontrib)
191 suntingan
Fitur saranan suntingan: 2 pranala ditambahkan.
 
(7 revisi perantara oleh 4 pengguna tidak ditampilkan)
Baris 1:
[[Berkas:Finite_element_sparse_matrix.png|ka|jmpl|Matriks rongga yang didapatkan ketika menyelesaikan [[metode elemen hingga]] dalam dua dimensi. Elemen matriks yang tidak bernilai nol ditandai oleh warna hitam.]]
{{Unreferenced|date=September 2019}}
Dalam [[analisis numeris|analisis numerik]] dan [[komputasi]], '''matriks''' '''jarangrongga''' adalah [[Matriks (matematika)|matriks]] di manayang sebagian besar elemenelemennya adalahbernilai nol. Sebaliknya, jika sebagian besar elemennya bukan nol, maka matriksnyamatriks tersebut dianggap '''padat'''. JumlahTidak elemenada bernilaidefinisi nolpasti dibagiberapa dengan jumlah totalbanyak elemen (misalnya,nol myang × ndiperlukan untuk matriks m × n) disebutdianggap '''jarang'rongga'', darinamun matrikskriteria (yang sering digunakan adalah banyaknya elemen yang tidak nol kurang lebih sama dengan 1banyaknya dikurangikolom atau baris pada matriks. '''kepadatan'Sparsity'' dari matriks). Menggunakandidefinisikan definisi-definisisebagai itu,rasio sebuahbanyaknya matrikselemen akanyang jarangbernilai ketikanol sparsity-nyadengan lebihbanyakn besarsemua darielemen 0matriks (contoh,5 m × n untuk matriks berukuran m × n).
 
Secara konseptual, sparsity berhubungan dengan sistem dengan sedikit interaksi berpasangan. PertimbangkanSebagai gariscontoh, pertimbangkan bola-bola yang disusun berbaris dan dihubungkan oleh pegas dari satu ke yang berikutnya: ini adalah contoh sistem yang jarangrongga karena hanya bola-bola yang berdekatansaling bersebelahan saja yang digabungkan. Sebaliknya, jika garissetiap bola yang sama memiliki mata airpegas-pegas yang menghubungkandihubungkan setiapke bola dengan semuabanyak bola lainnya, sistem akantersebut sesuaiberkorespondensi dengan matriks yang padat. Konsep sparsity berguna dalam [[kombinatorika]], dan areamemiliki aplikasipenerapan pada bidang seperti [[teori jaringan]], dan [[analisis numerik]]; yang memilikiumumnya kepadatanberurusan rendahdengan sistem dengan kepadatan data atau koneksi yang signifikanrendah. Matriks rongga besar sering muncul dalam aplikasi [[Ilmu|ilmiah]] atau [[Teknik|rekayasa]] ketika memecahkan [[persamaan diferensial parsial]].
 
Ketika menyimpan dan memanipulasi matriks rongga di [[komputer]], cukup bermanfaat dan seringkali diperlukan untuk menggunakan [[algoritme]] khusus dan [[struktur data]] yang menggunakan keuntungan dari struktur matriks rongga. Komputer yang terspesialisasi telah dibuat untuk berurusan dengan matriks rongga,<ref>{{Cite web|date=2019-08-19|title=Cerebras Systems Unveils the Industry’s First Trillion Transistor Chip|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-the-Industry%E2%80%99s-First-Trillion-Transistor-Chip|website=www.businesswire.com|language=en|access-date=2021-03-04|quote=WSE memiliki 400.000 ''compute cores'' yang dioptimalkan untuk AI. Disebut dengan SLAC™, singkatan dari ''Sparse Linear Algebra Cores'', ''compute cores'' bersifat fleksibel, dapat diprogram, dan dioptimalkan untuk aljabar linier [matriks] jarang yang mendukung semua komputasi ''neural network''}}</ref> karena mereka sering ditemui dalam bidang [[pemelajaran mesin]].<ref>{{Cite web|title=Argonne National Laboratory Deploys Cerebras CS-1, the World’s Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer|website=www.anl.gov|language=en|access-date=2021-03-04|quote=WSE adalah chip terbesar yang pernah dibuat dengan luas 46.225 milimeter persegi, 56,7 kali lebih besar dari unit pengolah grafis terbesar. Chip ini berisi 78 kali lebih banyak ''compute core'' yang dioptimalkan untuk AI, kecepatan yang 3.000 kali lebih tinggi, memori ''on-chip'', bandwidth memori yang 10.000 kali lebih banyak, dan bandwidth komunikasi yang 33.000 kali lebih banyak.}}</ref> Operasi yang menggunakan struktur matriks biasa dan algoritma yang standar akan lebih lambat dan tidak efisien, bila diterapkan pada matriks rongga karena pemrosesan dan [[Memori (komputer)|memori]] terbuang sia-sia. Data yang secara alami bersifat rongga lebih mudah [[Kompresi data|dikompresi]] dan karenanya membutuhkan [[Penyimpanan data komputer|penyimpanan]] yang jauh lebih sedikit. Beberapa matriks rongga yang berukuran sangat besar tidak dapat dimanipulasi dengan menggunakan algoritma matriks padat yang umum.
Matriks jarang besar sering muncul dalam aplikasi [[Ilmu|ilmiah]] atau [[Teknik|rekayasa]] ketika memecahkan [[persamaan diferensial parsial]].
 
== Contoh ==
Ketika menyimpan dan memanipulasi matriks jarang pada [[komputer]], itu bermanfaat dan sering diperlukan untuk menggunakan [[algoritme]] khusus dan [[struktur data]] yang mengambil keuntungan dari struktur matriks yang jarang. Operasi yang menggunakan struktur matriks padat dan algoritma lambat dan tidak efisien bila diterapkan pada matriks kecil yang jarang karena pemrosesan dan [[Memori (komputer)|memori]] terbuang sia-sia. Data yang jarang secara alami lebih mudah di[[Kompresi data|kompresi]] dan karenanya membutuhkan [[Penyimpanan data komputer|penyimpanan]] yang jauh lebih sedikit. Beberapa matriks jarang sangat besar tidak mungkin dimanipulasi menggunakan algoritma matriks padat standar.
Berikut adalah contoh matriks rongga, yang hanya mengandung 9 elemen tidak bernilai nol, dan 26 elemen bernilai nol. Nilai ''sparsity''-nya adalah 74%, dan kepadatannya 26%.
 
:<math>\left(\begin{matrix}
11 & 22 & 0 & 0 & 0 & 0 & 0 \\
0 & 33 & 44 & 0 & 0 & 0 & 0 \\
0 & 0 & 55 & 66 & 77 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 88 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 99 \\
\end{matrix}\right)</math>
 
== Struktur khusus ==
 
=== Pita ===
{{main article|Matriks pita}}Bentuk khusus matriks rongga yang penting adalah [[matriks pita]], yang didefinisikan sebagai berikut. [[Lebar pita]] bawah dari matriks <math>A</math> adalah bilangan {{math|''p''}} terkecil sehingga elemen <math>a_{ij}=0</math> jika {{math|''i'' > ''j'' + ''p''}}. Serupa dengan itu, lebar pita atas adalah bilangan {{math|''p''}} terkecil sehingga elemen <math>a_{ij}=0</math> jika {{math|''i'' < ''j'' − ''p''}} {{harv|Golub|Van Loan|1996|loc=§1.2.1}}. Sebagai contoh, [[matriks tridiagonal]] memiliki lebar pita bawah 1 dan lebar pita atas 1. Contoh lain, matriks rongga berikut memiliki lebar pita bawah dan atas bernilai 3. Elemen bernilai nol ditandai oleh simbol titik untuk memperjelas maksud.
 
: <math>
\left(
\begin{smallmatrix}
X & X & X & \cdot & \cdot & \cdot & \cdot & \\
X & X & \cdot & X & X & \cdot & \cdot & \\
X & \cdot & X & \cdot & X & \cdot & \cdot & \\
\cdot & X & \cdot & X & \cdot & X & \cdot & \\
\cdot & X & X & \cdot & X & X & X & \\
\cdot & \cdot & \cdot & X & X & X & \cdot & \\
\cdot & \cdot & \cdot & \cdot & X & \cdot & X & \\
\end{smallmatrix}
\right)
</math>
 
Matriks dengan lebar pita yang cukup kecil seringkali memiliki algoritme yang lebih sederhana ketimbang matriks rongga secara umum; atau seseorang dapat menerapkan algoritme matriks padat dan meningkatkan efisiensi cukup dengan membatasi [[iterasi]] indeks yang dilakukan.
 
Matrices with reasonably small upper and lower bandwidth are known as band matrices and often lend themselves to simpler algorithms than general sparse matrices; or one can sometimes apply dense matrix algorithms and gain efficiency simply by looping over a reduced number of indices.
 
Dengan menyusun ulang baris dan kolom dari matriks <math>A</math>, dimungkinkan untuk mendapatkan matriks <math>A'</math> dengan lebar pita yang lebih kecil. Beberapa algoritma dikembangkan untuk [[Lebar pita graf|minimalisasi lebar pita]].
 
=== Diagonal ===
[[Matriks diagonal]] merupakan kasus ekstrem dari matriks pita, dan memiliki struktur penyimpanan yang sangat efisien. Hal ini dilakukan cukup menyimpan elemen-elemen pada [[diagonal utama]] sebagai sebuah [[Larik|larik satu dimensi]], sehingga diagonal dari matriks berukuran {{math|''n'' × ''n''}} cukup memerlukan {{math|''n''}} elemen.
 
=== Simetris ===
Matriks simetris rongga muncul sebagai [[matriks ketetanggaan]] dari [[graf tak berarah]]; dan dapat disimpan secara efisien sebagai [[daftar ketetanggaan]].
 
=== Diagonal balok ===
[[Matriks diagonal balok]] terdiri dari sub-submatriks sepanjang diagonal utamanya. Matrik diagonal balok <math>A</math> memiliki bentuk
 
: <math>A = \begin{bmatrix}
A_1 & 0 & \cdots & 0 \\
0 & A_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & A_n
\end{bmatrix},</math>
 
dengan <math>A_k</math> adalah [[matriks persegi]], untuk ''k'' = 1, ..., ''n''.
 
== Referensi ==
<references />
 
{{Kelas matriks}}
 
{{Authority control}}
 
[[Kategori:Matematika]]
[[Kategori:Struktur data]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Matriks_rongga"