Aplikasi multiplisitas akar-akar dalam menentukan faktor persekutuan terbesar sistem polinomial

Abstract

Pada terapan matematika, banyak masalah dalam kasus nyata dapat dimodelkan ke dalam bentuk persamaan polinomial. Suatu metode atau algoritma yang efektif, akurat, dan efisien tentunya diperlukan untuk menyelesaikan persamaan polinomial tersebut, dalam hal ini mendapatkan bentuk faktorisasi dari polinomial yang diberikan. Dalam proses faktorisasi polinomial, akar memegang peranan penting, demikian pula halnya dengan multiplisitas akarnya. Pada tulisan ini dibahas suatu algoritma faktorisasi dengan cara manipulasi aljabar sederhana pada koefisien-koefisien polinomial yang ada tanpa menghitung akar-akarnya, yaitu algoritma faktorisasi polinomial berdasarkan multiplisitas akar-akarnya. Tulisan ini bertujuan untuk mempelajari proses faktorisasi polinomial tersebut dan pengembangan dari proses ini, yaitu mendapatkan algoritma penghitungan faktor persekutuan terbesar (GCD, greatest common divisor) sistem polinomial, serta menganalisis kedua algoritma yang terbentuk dalam kedua proses tersebut untuk mendapatkan kompleksitas waktu komputasinya. Hasil dari proses faktorisasi polinomial awal difaktorkan ke dalam bentuk perkalian polinomial- polinomial faktor dengan pangkat-pangkatnya sama dengan multiplisitas akar-akarnya, dan adaptasi dari proses ini, yaitu pengembangannya berguna dalam menghitung GCD sistem polinomial. Hasil dari analisis terhadap algoritma faktorisasi polinomial dan penghitungan GCD sistem polinomial memiliki kompleksitas waktu komputasi berturut-turut sebesar (5) dan O(n), dengan n menyatakan pangkat polinomial.