kompleksitas waktu di riset kimia komputasi

Hal yang selalu dinanti-nanti oleh seorang computational chemist adalah kapan proses optimasi akan selesai? Berapakah kira waktu yang diperlukan untuk sebuah proses optimasi? Menunggu adalah pekerjaan yang mendebarkan dalam riset di kimia komputasi (paling tidak ini pengalamanku pas skripsi, apalagi jika listrik tidak stabil dan sering mati). Bagaimanakah lamanya waktu optimasi naik seiring dengan kompleksitas perhitungan optimasi geometri.

Time complexity atau kompleksitas waktu adalah sebuah cara untuk menggambarkan bagaimana penggunaan CPU (prosesor, memori, hard disk) berubah seiring dengan perubahan masalah yang dihitung. Sebagai contoh, sebuah perhitungan ab initio HF dengan N orbital. Pada akhir perhitungan, semua energi orbital harus ditambahkan sehingga akan ada N operasi penambahan. Terdapat juga sejumlah set operasi yang tidak bergantung pada ukuran perhitungan seperti inisialisasi variabel dan pengalokasian memori yang kita sebut dengan C. algoritma standar untuk inversi matrix, N^3. Perhitungan integral Coulomb dua elektron dan integral pertukaran untuk ab initio HF setara dengan N^4, sehingga total resources CPU yang diperlukan meningkat dengan skala N^4 + N^3 + N + C. Biar bagaimanapun, harga N^3, N, dan C tidaklah terlalu besar bila dibandingkan dengan N^4. Computer scientist mendefinisikan jenis algoritma ini sebagai time complexity dari N^4. Analisis yang sama seharusnya juga dapat digunakan untuk penggunaan memory, disk, komunikasi dalam jaringan dll.

Lama waktu inilah yang menjadi ganjalan bagi peneliti di bidang kimia komputasi terutama jika resources komputasi yang dimiliki terbatas. Pengalaman waktu mengerjakan skripsi kemarin membuktikan bahwa keinginan untuk mendapatkan hasil yang tinggi dengan sumber komputasi yang terbatas malah membawa ke running yang tidak efektif, sudah memakan waktu lama, tapi hasil yang diperoleh tidak seberapa. Oleh karena itu, satu hal yang bisa kusimpulkan adalah ide komputasi selalu dibatasi oleh perangkat komputasi yang dimiliki. Jika perangkat komputasi yang dimiliki hanya pas-pasan, jangan harap bisa running molekul besar dengan metode tingkat tinggi, apalagi memodelkan dalam padatan. Belum lagi dengan kendala klasik di Indonesia yang sering mati listrik atau aliran listrik yang tidak stabil. Hal ini malah membuat semakin stress dalam mengerjakan penelitian.

Ada banyak algoritma berbeda yang digunakan di setiap program untuk mendapatkan hasil yang sama sehingga waktu yang diperlukan oleh masing-masing program kimia komputasi dapat berbeda antara satu program dengan yang lain. Tabel di bawah ini menunjukkan skala waktu yang diperlukan untuk perhitungan kimia komputasi, di mana N adalah jumlah orbital dalam perhitungan, A adalah jumlah active space dalam perhitungan CASSCF, M adalah jumlah atom, L adalah panjang satu sisi box dalam PBC dan tentu saja harga N akan naik dengan bertambahnya jumlah atom atau menggunakan basis set yang lebih besar.

Tabel kompleksitas waktu komputasi untuk beberapa metode kimia komputasi


Optimasi geometri membutuhkan waktu yang lebih lama daripada single point dikarenakan dua alasan, pertama banyak perhitungan yang harus dilakukan jika geometri berubah. Kedua, masing-masing iterasi membutuhkan waktu untuk menghitung gradien energi. Waktu yang diperlukan untuk optimasi, T_opt tergantung pada derajat kebebasan, D. derajat kebebasan adalah variabel geometri yang dihitung seperti panjang ikatan, sudut, dihedral dll. Meskipun kita melakukan fix atom tetap saja tidak bisa mengurangi harga derajat kebebasan. Gampannya, waktu yang diperlukan untuk optimasi dapat diperkirakan dari waktu yang diperlukan untuk single point dengan rumus.


Untuk perhitungan ab initio, semi empiris atau dinamika molekular, CPU merupakan faktor pertama yang menjadi perhatian bagi peneliti. Untuk molekul besar, memori merupakan faktor yang harus diperhatikan untuk perhitungan mekanika molekular. Tabel di bawah menunjukkan memori yang diperlukan untuk beberapa algoritma geometri optimasi.

Tabel kebutuhan memori untuk algoritma optimasi


Time complexity hanya mengindikasikan bagaimana kebutuhan CPU bertambah seiring dengan naiknya ukuran sistem. Namun demikian, sistem yang kecil yang dihitung dengan metode yang kompleks pun juga membutuhkan waktu yang lama untuk selesai. Metode yang memakan waktu lama semakin membutuhkan perangkat komputasi yang tinggi.

Karena optimasi geometri memakan waktu yang lama, maka dari itu sering digunakan dua metode yang berbeda untuk satu jenis sistem yang dikaji. Misalnya metode ab initio HF dengan basis set yang tidak terlalu besar dan koreksi minimal digunakan untuk optimasi kemudian metode yang lebih tinggi dan basis set yang lebih besar digunakan untuk perhitungan single point pada struktur yang telah teroptimasi tadi. Metode ini sering ditulis dengan notasi sebagai berikut :
MP2/6-31G*//CCSD(T)/cc-pVTZ
artinya optimasi geometri dilakukan menggunakan MP2 dengan basis set 6-31G* dan perhitungan akhir energi dilakukan dengan single point menggunakan CCSD(T) dengan basis set cc-pVTZ. Bisa juga perhitungan optimasi geometri menggunakan mekanika molekular atau semi empiris digunakan sebagai langkah untuk mendapatkan geometri awal bagi perhitungan ab initio HF. Sebagai catatan, banyak program yang sekarang menggunakan algoritma direct integral yang untuk hardware saat ini lebih baik daripada algoritma konvensional, namun algoritma SCF yang tercepat adalah in core, akan tetapi hal ini harus dibayar dengan penggunaan memori yang sangat besar.

Apa yang bisa disimpulkan dari uraian di atas? Penelitian dalam bidang komputasi membutuhkan perencanaan yang matang, baik perangkat komputasi yang diperlukan, akurasi hasil akhir yang ingin dicapai, waktu yang diperlukan dan kesesuaian metode yang digunakan dengan perangkat komputasi yang dimiliki. Jangan sampai waktu yang diperlukan lama, tapi hasil yang diperoleh sedikit. Oke, sekian dulu tentang bahasan time complexity dalam penelitian kimia komputasi, semoga bermanfa’at!

# Young, D. C, 2001, Computational Chemistry: A Practical Guide for Applying Techniques to Real-World Problems,  John Wiley & Sons,  New York.

# rule of thumb in geometry optimization are geometry optimization will be faster if your structure is near the local minimum and your initial guess is correct for geometry optimization.

One thought on “kompleksitas waktu di riset kimia komputasi

  1. Pingback: pra optimasi bagian 1 « neax502 simple blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s