Implementasi Basis Gröbner pada Sistem Polinomial Nonlinear Multivariat Biner dengan Rekurensi Divide and Conquer

Abstract

Membahas suatu sistem persamaan polinomial umumnya berkaitan dengan menentukan solusi yang memenuhi sistem tersebut. Dalam ring polinomial multivariat, salah satu metode dalam menentukan solusi persamaan khususnya pada ring polinomial nonlinear multivariat biner adalah menggunakan suatu basis, yang disebut basis Gröbner. Basis ini berasal dari suatu ideal di dalam ring polinomial tersebut. Untuk mencari basis ini, akan digunakan algoritme Buchberger. Algoritme ini diterapkan pada sistem polinomial biner dengan setiap polinomialnya dapat direpresentasikan dalam simbol sebagai set of set of integers. Karena memerlukan iterasi yang cukup banyak dalam proses komputasinya, selanjutnya dimodifikasi dengan menerapkan metode rekurensi divide and conquer. Ide dasar modifikasi ini yakni membagi problem menjadi subproblem hingga yang terkecil, kemudian diselesaikan secara rekursif dengan melibatkan algoritme Buchberger pada saat proses penggabungannya. Penerapan algoritme pada pemrograman MAPLE menunjukkan bahwa metode modifikasi algoritme Buchberger dan divide and conquer jauh kebih cepat dari metode hanya menerapkan algoritme Buchberger.