Pratama, Theo (2018) Desain Dan Analisis Algoritma Komputasi Matriks Yang Mengandung Matriks Toeplitz Dengan FFT. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5114100029-Undergraduate_Theses.pdf - Accepted Version Download (1MB) | Preview |
Abstract
Diberikan suatu konfigurasi warna kucing melingkar sepanjang N dan banyaknya putaran komunikasi barisan kucing sebanyak K. Untuk setiap komunikasi, kucing-kucing tersebut berubah warna. Transformasi perubahan warna ini dimodelkan menjadi suatu matriks transformasi sebesar N x N tetapi banyaknya pemangkatan yaitu K mencapai 109 dan besarnya matriks transformasi mencapai 50000 sehingga algoritma perkalian secara umum dengan kompleksitasO(N3) dan pemangkatan matriks pada umumnya kurang cepat untuk menyelesaikan permasalahan ini. Pada permasalahan ini juga terdapat sifat khusus dimana matriks transformasi ini memiliki submatriks berjenis Matriks Toeplitz dan jika matriks ini dilakukan perkalian, matriks ini selalu konsisten menghasilkan matriks dengan struktur yang serupa. Pada tugas akhir ini akan dirancang penyelesaian masalah dengan melakukan pemodelan masalah seperti yang sudah dijelaskan pada paragraf pertama. Matriks transformasi yang terbentuk akan dilakukan perkalian menggunakan konvolusi, Fast Fourier Transform, dan pemangkatan secara modular dalam penyelesaiannya. Solusi yang dikembangkan berjalan dengan kompleksitas waktu O(N log N logK), dimana N merupakan besarnya matriks transformasi dan K merupakan besarnya pemangkatan matriks. Solusi ini berhasil melakukan komputasi matriks dengan substruktur Matriks Toeplitz dengan sangat cepat dibandingkan dengan perkalian dan pemangkatan matriks secara umum.
==================================================================================================
Given a set configuration of cat’s color in circular line with length N and K which K is the amount of circular communication from the line of cats. For each communication, the color of cat will be transformed into a certain color. Transformation of these color will be modeled into a transformation matrix with size N � N and theamount of power K. K has upper bound constraint 109 and the the size of matrix will be as huge as 50000 so the naive algorithm with complexity O(N3) and general matrix exponentiation don’t fast enough to solve this problem. For problem, there is a specific behavior which is this matrix has a Toeplitz Matrix as a sub-matrix and if this matrix is multiplied together, this matrix will be consistent producing a matrix with same structure. In this final project the writer will design and analyze a solution to solve the problem that stated in first paragraph. The transformation matrix will multiplied with convolution, Fast Fourier Transform, and modular exponent for the computation. The developed solution run with complexity timeO(N log N logK) which N is a size of transformation matrix and K is size of the power of matrix. The solution show very fast performance than general matrix multiplication and exponentiation.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.74 Pra d 3100018074707 |
| Uncontrolled Keywords: | konvolusi; Matriks Toeplitz; matriks transformasi; FFT; convolution; Toeplitz Matrix; transformation matrix |
| Subjects: | Q Science > QA Mathematics > QA404 Fourier series Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. T Technology > T Technology (General) |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Theo Pratama |
| Date Deposited: | 20 Mar 2018 02:44 |
| Last Modified: | 10 Sep 2020 07:27 |
| URI: | http://repository.its.ac.id/id/eprint/50505 |
Actions (login required)
 |
View Item |