Vol. 17, No. 3,  349-356,  May, 2021 DOI: 10.20956/j.v17i3.12490

## Solving Ordinary Differential Equation Using Parallel Seventh Order Runge-Kutta Method with Two Processors

## Penyelesaian Persamaan Diferensial Biasa Menggunakan Metode Runge- Kutta Orde Ketujuh Paralel dengan Dua Prosesor
Iman Al Fajri 1* , Hendra 2* , Jeffry Kusuma 3*

## Abstract
This paper presents a derivation of the seventh order Runge-Kutta method with eight stages suitable for parallel implementation.  The  development  of  a  parallel  model  is  based  on  the  second  type  of  Runge-Kutta  sparsity structure  which  is  divided  into  two  processors  by  creating  a  semi-implicit  version  of  the  sequential  seventh order Runge-Kutta which is solved through nine stages. The parallelization simulation implementation uses the Ray  module  in  the  Python  programming  language  by  giving  a  0.01  second  delay  for  each  completed  stage. Comparison of the calculation of the parallel model and the sequential model in terms of accuracy shows the same results, even in some cases, parallel is better. It is generally seen that the parallel method will approach the analytical solution by increasing the number of iterations. In terms  of execution time, parallel method has advantage over sequential method.
Keywords : Seventh Order Runge-Kutta Method, Parallel Algorithm, Sequential Algorithm

## Abstrak
Makalah ini menyajikan penurunan dari metode Runge-Kutta orde ketujuh dengan delapan tahapan yang cocok untuk implementasi secara paralel. Pengembangan model paralel didasarkan pada struktur sparsity Runge-Kutta tipe  kedua  yang  dibagi  ke  dalam  dua  prosesor  dengan  membuat  versi  semi  implisit  dari  Runge-Kutta  orde ketujuh  sekuensial  yang  diselesaikan  melalui  sembilan  tahapan.  Implementasi  simulasi  paralelisasi menggunakan  modul  Ray  pada  bahasa  pemrograman  Python  dengan  memberi  delay  0.01  detik  untuk  setiap tahapan  yang  diselesaikan.  Perbandingan  perhitungan  model  paralel  dan  model  sekuensial  dari  sisi  akurasi menunjukkan  hasil  yang  sama,  bahkan  pada  beberapa  kasus,  paralel  lebih  baik.  Terlihat  secara  umum  bahwa metode  paralel  akan  mendekati  solusi  analitik  dengan  meningkatkan  jumlah  iterasi.  Ditinjau  dari  sisi  waktu eksekusi, metode paralel memiliki keunggulan dibandingkan dengan metode sekuensial.
Kata kunci : Metode Runge-Kutta Orde Ketujuh, Algoritma Paralel, Algoritma Sekuensial

## 1. Pendahuluan
Algoritma  paralel  adalah  salah  satu  metode  untuk  menyelesaikan  masalah  numerik.  Masalah numerik  merupakan  salah  satu  masalah  yang  memerlukan  kecepatan  komputasi  yang  cukup  tinggi. Dalam ilmu komputer, sebuah algoritma paralel atau algoritma bersamaan, sebagai lawan sekuensial, merupakan  algoritma  yang  dapat  dieksekusi  sepotong  pada  suatu  waktu  dan  pada  banyak  perangkat
* Program Studi Magister Matematika, FMIPA-UNHAS
Email : 1 iman.alfajri@gmail.com, 2 hendra.unhas@gmail.com, 3 jeffry.kusuma@gmail.com

## Jurnal Matematika, Statistika & Komputasi

## Iman Al Fajri, Hendra, Jeffry Kusuma
pengolahan yang berbeda, kemudian digabungkan bersama-sama lagi sehingga didapatkan hasil yang benar.
Ada  tingkatan  paralelisme  yang  bisa  digunakan  untuk  memecahkan  persamaan  diferensial  biasa secara numerik. Caranya adalah dengan restrukturisasi kode manual dan/atau kompilator paralelisasi. Ini  dapat  ditambah  dengan  mengganti  serial  dengan  paralel,  misalnya,  aljabar  linier.  Namun,  level- level paralelisasi ini mungkin tidak diharapkan menghasilkan banyak perbaikan karena banyak kode mungkin  masih  harus  berjalan  secara  serial.  Pendekatan  yang  lebih  bermanfaat  adalah  mendesain ulang sifat sekuensial dari algoritma yang digunakan untuk memecahkan persamaan diferensial  biasa menjadi algoritma paralel.
Metode  Runge-Kutta  adalah  salah  satu  metode  penyelesaian  persamaan  diferensial  dengan  nilai awal secara numerik. Metode ini dapat menghasilkan solusi yang memiliki akurasi yang cukup tinggi dibandingkan dengan metode lainnya.
Dalam  banyak  kasus,  persamaan  diferensial  tidak  dapat  dipecahkan  dalam  aspek  analitik. Tujuannya  adalah  untuk  menemukan  di  antara  metode  yang  ada,  metode  terbaik  untuk  resolusi numerik.  Juga  untuk  memfasilitasi  penerapan  metode  dengan  memperkenalkan  perangkat  lunak penghitungan.  Untuk  melakukan  ini,  digunakan  metode  Runge-Kutta  yang  merupakan  salah  satu metode resolusi numerik terbaik [10].
Publikasi  [3]  menganalisis  hubungan  koefisien  metode  Runge-Kutta  orde  ketiga  dan  orde keempat.  Hasilnya  adalah  metode  paralel  dapat  secara  bersamaan  memenuhi  hubungan  koefisien kedua  metode  tersebut.  Metode  ini  dapat  diimplementasikan  dalam  kerangka  multi-proses berdasarkan cluster. Metode tersebut diterapkan pada simulasi numerik integral prediksi orbit pesawat ruang  angkasa.  Hasil  eksperimen  menunjukkan  bahwa  keakuratan  metode  paralel  konsisten  dengan metode serial, dan kecepatan komputasi secara signifikan lebih tinggi daripada metode serial.
Implementasi  efisien  dari  metode  Runge-Kutta  implisit  untuk  menyelesaikan  sistem  besar persamaan  diferensial  biasa  dilakukan  dengan  memanfaatkan  blok  segitiga  bawah  dari  matriks kuadratur dan mengilustrasikannya secara numerik [1,5,9]. Runge-Kutta implisit diagonal diterapkan pada  persamaan  diferensial  biasa  orde  pertama  dengan  menggunakan  Runge-Kutta  orde  keempat sampai orde keenam dengan dua sampai tujuh tahapan [7].

## 2. Metode Runge-Kutta Orde Ketujuh Paralel

## Bentuk umum persamaan diferensial biasa orde pertama dengan nilai awal adalah
( )    (    )          ( ) (2.1)
Bentuk umum metode Runge-Kutta s-tahap untuk masalah (2.1) didefinisikan sebagai [4]
∑ (2.2)
di mana
( ∑ ) (2.3)
dengan mengasumsikan sebagai berikut.
Iman Al Fajri, Hendra, Jeffry Kusuma
∑
(2.4)
Koefisien  pada  persamaan  (2.2)  dan  (2.3)  dapat  ditampilkan  dengan  menggunakan  tabel Butcher sebagai berikut [2].
Tabel 2.1. Tabel Butcher
Untuk metode Runge-Kutta orde ketujuh dengan 9-tahap dirumuskan sebagai berikut.
∑ (2.5)
Sedangkan solusi eksak untuk persamaan (2.5) adalah
( ∑ )    ( ) (2.6)
Koefisien  pada  persamaan  (2.2)  dan  (2.3)  direprentasikan  dengan  Array  Butcher  atau  Tabel Butcher seperti pada Tabel 2.2 berikut.
Tabel 2.2. Tabel Butcher 9-tahap Orde Ketujuh
Metode ini  dikatakan  eksplisit jika
untuk ,  semi  implisit jika untuk , selain itu dikatakan sepenuhnya implisit. Kajian ini secara khusus membahas tentang metode Runge- Kutta dengan sifat semi implisit.
Rumusan  Runge-Kutta  orde  ketujuh  serial  [2]  menggunakan  metode  dengan  9  tahapan  sebagai berikut.
Tabel 2.3. Tabel Butcher 9-tahap Orde Ketujuh Sekuensial

## Jurnal Matematika, Statistika & Komputasi
Iman Al Fajri, Hendra, Jeffry Kusuma

## 3. Metode Paralel Tipe II
Tabel Butcher untuk metode orde keenam tipe II diberikan oleh Tabel 3.1 berikut [2].
Tabel 3.1. Tabel Butcher 8-tahap Orde Ketujuh Tipe II
Struktur  ketersebaran  metode  tipe  II  diperluas  untuk  mendapatkan  metode  Runge-Kutta  orde tinggi yang merupakan orde ketujuh dengan delapan evaluasi fungsional. Struktur baru disajikan pada Gambar 3.1 bersama dengan digrafnya [6].
Matriks Runge-Kutta
Digraf
(

## Jurnal Matematika, Statistika & Komputasi
Iman Al Fajri, Hendra, Jeffry Kusuma
Gambar 3.1. Struktur Ketersebaran dan Digraf untuk Metode Runge- Kutta Orde Ketujuh dengan Delapan Tahapan
Formulasi Runge-Kutta untuk tabel Butcher 8-tahap orde ketujuh Tipe II tersebut adalah
∑ (3.1)
di mana
( ( )) (3.2) (
( )) ( ( )) ( ( )) ( ( )) ( ( )) ( ( )) ( ( ))
Untuk  mendapatkan  metode  Runge-Kutta  orde  ketujuh  paralel  8  tahapan,  digunakan  rumusan metode Runge-Kutta sekuensial pada Tabel 2.2 yang diubah menjadi diagonal semi implisit. Sehingga diperoleh persamaan sebagai berikut.
( ) (3.3)
di mana
( ( ) ( ) )
(3.4)
( ( ) ( ) )
( ( ) ( ) ( ) ( ) )
( ( ) ( ) ( ) ( ) ) ( ( ) ( ) ( ) ( ) ( ) ( ) ) ( ( ) ( ) ( ) ( ) ( ) ( ) )

## Jurnal Matematika, Statistika & Komputasi

## Iman Al Fajri, Hendra, Jeffry Kusuma
( ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ) ( ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) )
Diperoleh rumusan metode Runge-Kutta orde ketujuh dengan 8 tahapan pada persamaan (3.3) dan (3.4) yang siap dipakai untuk menyelesaikan persamaan diferensial. Untuk menguji keandalan metode Runge-Kutta yang ditemukan, akan digunakan pada beberapa kasus di bawah ini.

## 4. Beberapa Masalah yang Diuji
Soal 5.1 [8] :

## (  )
( )
Solusi eksak : ( )
Soal 5.2 [8] :
( )
( )
Solusi Eksak :

## 5. Hasil Perhitungan Numerik
Tabel 6.1. Nilai Galat Global Maksimum (GGM) Soal 5.1 dan 5.2 antara Metode Paralel dan Metode Sekuensial Dibandingkan dengan Solusi Analitik Soal Metode GGM 5.1 RK4 Sekuensial RK4 Paralel 5.062616992E-14 5.062616992E-14 1.243449788E-14 1.243449788E-14 1.687538997E-14 1.687538997E-14 8.082423619E-14 8.082423619E-14 5.2 RK4 Sekuensial RK4 Paralel 7.481309556E-02 1.837075818E-02 7.892880887E-03 1.548182798E-03 7.931475369E-04 1.528469541E-04 7.935300051E-05 1.526537343E-05
Selanjutnya Tabel 6.2 dan 6.3 menunjukkan waktu  eksekusi sekuensial dan paralel untuk masing- masing masalah yang diselesaikan. Proses ini menggunakan komputer dengan spesifikasi intel core i3 yang  diatur  untuk  menggunakan  dua  prosesor  dengan  memori  4  (empat)  GB.  Paralelisasi  diatur dengan modul Ray dari bahasa pemrograman Python.
Perhitungan  diimplementasikan  pada  algoritma  paralel  dan  diberikan  waktu  delay  0.01  detik untuk setiap persamaan yang dieksekusi. Hal ini bertujuan untuk menerapkan konsep paralelisasi yang telah digambarkan pada Tabel 3.1. Waktu delay 0.01 detik juga diterapkan pada algoritma sekuensial sebagai pembandingnya.

## Jurnal Matematika, Statistika & Komputasi
Iman Al Fajri, Hendra, Jeffry Kusuma
Tabel 6.2. Waktu Eksekusi untuk Soal 5.1
Waktu Eksekusi Sekuensial (detik) Waktu Eksekusi Paralel (detik) 10 0.827968 0.682974 100 7.668562 5.774143 1000 76.615609 58.392098 10000 755.883317 558.092867 Tabel 6.3. Waktu Eksekusi untuk Soal 5.2 Waktu Eksekusi Sekuensial (detik) Waktu Eksekusi Paralel (detik) 10 0.8332850 0.6645990 100 7.6863380 6.1695970 1000 76.2234060 55.7306180 10000 752.7016530 556.7977500

## 6. Kesimpulan
Perbandingan nilai galat global maksimum antara metode sekuensial, paralel, dan solusi analitik adalah  bahwa  metode  Runge-Kutta  orde  ketujuh  paralel  menunjukkan  akurasi  yang  sama dibandingkan  dengan  metode  sekuensial.  Dalam  beberapa  kasus,  akurasi  paralel  lebih  baik  daripada sekuensial.  Secara  umum  bahwa  dari  seluruh  soal  yang  diselesaikan,  metode  Runge-Kutta  orde ketujuh  paralel  sudah  mendekati  nilai  perhitungan  solusi  analitik  apabila  iterasinya  semakin ditingkatkan.
Perbandingan  waktu  eksekusi,  percepatan,  dan  efisiensi  algoritma  sekuensial  dan  algoritma sekuensial  terlihat  bahwa untuk  setiap  peningkatan jumlah  iterasi,  waktu  eksekusi  paralel lebih baik daripada waktu eksekusi sekuensial.

## Daftar Pustaka
[1]  Axelsson,  O,  dan  Neytcheva,  M.  2020.  Numerical  Solution  Methods  for  Implicit  Runge-Kutta Methods  of  Arbitrarily  High  Order. In:  Proceedings  of  the  conference  'Algoritmy  2020' Vydavateľstvo SPEKTRUM, Slovak University of Technology in Bratislava , Vol. 7, pp. 11-20
[2]  Butcher,  J.C.  2008.  Numericals  Methods  for  Ordinary  Differential  Equations  Second  Edition.

## Jurnal Matematika, Statistika & Komputasi
Iman Al Fajri, Hendra, Jeffry Kusuma
Wiley : USA
[3] Cui, W., Li, Y., dan Sun, Z. 2019. A Parallel Computer Numerical Simulation Method Based on Coincident Coefficients. J. Phys.: Conf. Ser . 1486 042038
[4] Din, U.K.S., dan Ismail, F. 2011. Parallel Two-Processor Fifth Order Diagonally Implicit Runge- Kutta Method. Menemui Matematik , Vol. 33, No. 1 : 23
[5] Hatten, N. dan Russell, R. P. 2017. Parallel Implicit Runge-Kutta Methods Applied to Coupled Orbit/Attitude Propagation. Journal of the Astronautical Sciences , vol. 64, no. 4, pp. 333–360
[6]  Iserles,  A.    dan  Nørsett,  S.  P.    1990.  On  the  Theory  of  Parallel  Runge-Kutta  Methods. IMA  J. Numer. Anal. , vol. 10, no. 4, pp. 463–488
[7]  Kennedy,  C.A.,  dan  Carpenter,  M.H.  2016.  Diagonally  Implicit  Runge-Kutta  Methods  for Ordinary Differential Equations. A Review. NASA : Virginia
[8] Maya, Rippi. 2014. Diktat Kuliah Persamaan Diferensial Biasa Revisi Keenam. IKIP Siliwangi : Bandung
[9]  Pazner,  W.,  dan  Persson,  P.2017.  Stage-parallel  fully  implicit  Runge–Kutta  solvers  for discontinuous Galerkin fluid simulations. Journal of Computational Physics , Vol. 335
[10] Séka, H. dan Kouassi, A. R. 2019. A New Seventh Order Runge-kutta Family: Comparison with the Method of Butcher and Presentation of a Calculation Software. Math. Comput. Sci. , vol. 4, no. 3, p. 68