Polynomial root-finding algorithms
বহুপদী শিকড় খুঁজে পাওয়া একটি দীর্ঘস্থায়ী সমস্যা যা ইতিহাস জুড়ে অনেক গবেষণার বিষয় হয়ে দাঁড়িয়েছে। এর একটি প্রমাণ হল যে 19শ শতাব্দী পর্যন্ত বীজগণিত মূলত বহুপদী সমীকরণের তত্ত্বকে বোঝাত। মূলনীতি একটি রৈখিক বহুপদীর (ডিগ্রি এক) মূল খুঁজে বের করা সহজ এবং এর জন্য শুধুমাত্র একটি বিভাজনের প্রয়োজনঃ সাধারণ সমীকরণের সমাধান রয়েছে। তিন এবং চার ডিগ্রির জন্য, র্যাডিকেলের পরিপ্রেক্ষিতে ক্লোজ-ফর্ম সমাধান রয়েছে, যা সাধারণত সংখ্যাসূচক মূল্যায়নের জন্য সুবিধাজনক নয়, কারণ এটি খুব জটিল এবং বেশ কয়েকটি মূলের গণনার সাথে জড়িত যার গণনা পলিনোমিয়ালের মূলগুলির সরাসরি গণনার চেয়ে সহজ নয় (উদাহরণস্বরূপ, একটি কিউবিক পলিনোমিয়ালের প্রকৃত মূলগুলির অভিব্যক্তি অ-বাস্তব ঘনমূলের সাথে জড়িত হতে পারে)। পঞ্চম বা তার বেশি মাত্রার বহুপদের জন্য আবেল-রুফিনি উপপাদ্য দাবি করে যে, সাধারণভাবে মূলগুলির কোনও মৌলিক অভিব্যক্তি নেই। সুতরাং, খুব কম ডিগ্রি ব্যতীত, পলিনোমিয়ালগুলির মূল অনুসন্ধান মূলগুলির আনুমানিক সন্ধান নিয়ে গঠিত। বীজগণিতের মৌলিক উপপাদ্য অনুসারে, ডিগ্রির একটি বহুপদের সঠিক বাস্তব বা জটিল মূল থাকে যা গুণমান গণনা করে। এটি অনুসরণ করে যে পলিনোমিয়ালগুলির জন্য মূল খুঁজে পাওয়ার সমস্যাটি তিনটি ভিন্ন উপ-সমস্যায় বিভক্ত হতে পারে; একটি মূল খুঁজে বের করা সমস্ত শিকড় খুঁজে বের করা জটিল সমতলের একটি নির্দিষ্ট অঞ্চলে শিকড় খুঁজে বের করা, সাধারণত প্রকৃত শিকড় বা প্রদত্ত বিরতিতে প্রকৃত শিকড় (উদাহরণস্বরূপ, যখন শিকড়গুলি একটি ভৌত পরিমাণের প্রতিনিধিত্ব করে, তখন শুধুমাত্র প্রকৃত ধনাত্মকগুলি আকর্ষণীয় হয়)। একটি মূল খুঁজে বের করার জন্য নিউটনের পদ্ধতি এবং অন্যান্য সাধারণ পুনরাবৃত্তিমূলক পদ্ধতি সাধারণত ভাল কাজ করে। সমস্ত মূল খুঁজে বের করার জন্য, যুক্তিযুক্তভাবে সবচেয়ে নির্ভরযোগ্য পদ্ধতি হল ফ্রান্সিস কিউআর অ্যালগরিদম যা বহুপদের সাথে সম্পর্কিত কম্প্যানিয়ন ম্যাট্রিক্সের আইগেনভ্যালু গণনা করে, যা ম্যাটল্যাবে স্ট্যান্ডার্ড পদ্ধতি হিসাবে প্রয়োগ করা হয়। সমস্ত শিকড় খুঁজে বের করার প্রাচীনতম পদ্ধতি হল একটি একক শিকড় খুঁজে বের করা। যখন একটি মূল পাওয়া যায়, তখন দ্বিপদীকে ভাগ করে বহুপদী থেকে এটি অপসারণ করা যেতে পারে। ফলস্বরূপ পলিনোমিয়ালে অবশিষ্ট মূল থাকে, যা এই প্রক্রিয়ার পুনরাবৃত্তির মাধ্যমে পাওয়া যায়। তবে, নিম্ন মাত্রা ব্যতীত, সংখ্যাসূচক অস্থিতিশীলতার কারণে এটি ভালভাবে কাজ করে নাঃ উইলকিনসনের বহুপদী দেখায় যে একটি সহগের খুব ছোট পরিবর্তন নাটকীয়ভাবে কেবল মূলের মানই নয়, তাদের প্রকৃতিও (বাস্তব বা জটিল) পরিবর্তন করতে পারে। এছাড়াও, একটি ভাল আনুমানিকতার সাথেও, যখন কেউ একটি আনুমানিক মূলে একটি বহুপদ মূল্যায়ন করে, তখন কেউ এমন একটি ফলাফল পেতে পারে যা শূন্যের কাছাকাছি হতে পারে। উদাহরণস্বরূপ, যদি 20 মাত্রার একটি বহুপদীর (উইলকিনসনের বহুপদের মাত্রা) মূল 10-এর কাছাকাছি হয়, তবে মূলের বহুপদের অন্তরজ এই ক্রমের হতে পারে যা বোঝায় যে মূলের মানের একটি ত্রুটি আনুমানিক মূলের বহুপদের মান তৈরি করতে পারে যা এই ক্রমের। বর্তমানে সবচেয়ে কার্যকর পদ্ধতি হল অ্যাবার্থ পদ্ধতি। এম. পি. সলভ নামে একটি বিনামূল্যে বাস্তবায়ন পাওয়া যায়। এটি একটি রেফারেন্স বাস্তবায়ন, যা নিয়মিতভাবে 1,000-এর বেশি উল্লেখযোগ্য দশমিক অঙ্ক সহ 1,000-এর বেশি মাত্রার পলিনোমিয়ালের মূল খুঁজে পেতে পারে। সমস্ত মূল গণনা করার পদ্ধতিগুলি বাস্তব মূল গণনা করার জন্য ব্যবহার করা যেতে পারে। তবে, একটি ছোট কাল্পনিক অংশ সহ একটি মূল বাস্তব কিনা তা নির্ধারণ করা কঠিন হতে পারে। উপরন্তু, যেহেতু প্রকৃত মূলের সংখ্যা, গড়ে, ডিগ্রির লগারিদম, তাই বাস্তব মূলের প্রতি আগ্রহী হলে অ-বাস্তব মূল গণনা করা কম্পিউটার সম্পদের অপচয়। প্রকৃত মূলের সংখ্যা গণনা করার প্রাচীনতম পদ্ধতি এবং একটি ব্যবধানের মূলের সংখ্যা স্টর্মের উপপাদ্য থেকে প্রাপ্ত ফলাফল, তবে ডেসকার্টেসের চিহ্নের নিয়ম এবং এর সম্প্রসারণের উপর ভিত্তি করে পদ্ধতিগুলি-বুদান এবং ভিনসেন্টের উপপাদ্য-সাধারণত আরও কার্যকর। মূল খুঁজে বের করার জন্য, শূন্য বা একটি মূলযুক্ত ব্যবধান না পাওয়া পর্যন্ত মূলগুলি অনুসন্ধান করা হয় এমন ব্যবধানগুলির আকার হ্রাস করে সবাই এগিয়ে যায়। তারপর একটি মূল ধারণকারী ব্যবধানগুলি আরও হ্রাস করা যেতে পারে যাতে নিউটনের পদ্ধতির বিচ্ছিন্ন মূলগুলির সাথে দ্বিঘাত অভিসরণ পাওয়া যায়। প্রধান কম্পিউটার বীজগণিত ব্যবস্থাগুলিতে (ম্যাপেল, ম্যাথমেটিকা, সেজম্যাথ, প্যারি/জিপি) একটি পলিনোমিয়ালের আসল মূলগুলির জন্য ডিফল্ট অ্যালগরিদম হিসাবে এই পদ্ধতির প্রতিটি বৈকল্পিক রয়েছে। পদ্ধতির শ্রেণীটি বহুপদীর মূল খুঁজে বের করার সমস্যাটিকে বহুপদের সহচর ম্যাট্রিক্সের আইগেনভ্যালু খুঁজে বের করার সমস্যায় রূপান্তরিত করার উপর ভিত্তি করে, নীতিগতভাবে, বহুপদের মূল খুঁজে বের করার জন্য যে কোনও আইগেনভ্যালু অ্যালগরিদম ব্যবহার করতে পারে। যাইহোক, দক্ষতার কারণে একজন এমন পদ্ধতি পছন্দ করে যা ম্যাট্রিক্সের কাঠামোকে নিযুক্ত করে, অর্থাৎ, ম্যাট্রিক্স-মুক্ত আকারে প্রয়োগ করা যেতে পারে। এই পদ্ধতিগুলির মধ্যে রয়েছে শক্তি পদ্ধতি, যার সহচর ম্যাট্রিক্সের ট্রান্সপোজে প্রয়োগ হল সবচেয়ে বড় মডুলাসের মূল খুঁজে বের করার জন্য শাস্ত্রীয় বার্নৌলির পদ্ধতি। শিফট সহ বিপরীত শক্তি পদ্ধতি, যা প্রথমে কিছু ক্ষুদ্রতম মূল খুঁজে পায়, জেনকিন্স-ট্রব অ্যালগরিদমের জটিল (সিপোলি) রূপটিকে চালিত করে এবং এটিকে তার সংখ্যাসূচক স্থিতিশীলতা দেয়। উপরন্তু, গুচ্ছবদ্ধ শিকড়ের উপস্থিতিতেও এটির ক্রমের সাথে দ্রুত অভিসরণ রয়েছে (যেখানে স্বর্ণ অনুপাত)। এই দ্রুত অভিসরণ প্রতি ধাপে তিনটি বহুপদী মূল্যায়নের খরচ নিয়ে আসে, যার ফলে অবশিষ্টাংশ হয়, যা নিউটনের পদ্ধতির তিনটি ধাপের তুলনায় ধীর অভিসরণ। একটি মূল খুঁজে বের করা একটি মূল গণনা করার জন্য সর্বাধিক ব্যবহৃত পদ্ধতি হল নিউটনের পদ্ধতি, যা একটি ভাল-নির্বাচিত মান থেকে শুরু করে গণনার পুনরাবৃত্তি নিয়ে গঠিত যদি এটি একটি বহুপদী হয়, প্রতিটি পুনরাবৃত্তিতে বহুপদী এবং এর ব্যুৎপত্তি গণনা করার জন্য পূর্বপ্রক্রিয়াকরণের সাথে হর্নারের পদ্ধতি বা মূল্যায়ন ব্যবহার করার সময় গণনা দ্রুত হয়। যদিও অভিসরণ সাধারণত দ্বিঘাত, এটি খুব ধীরে ধীরে একত্রিত হতে পারে বা এমনকি মোটেও একত্রিত হতে পারে না। বিশেষত, যদি পলিনোমিয়ালটির কোনও বাস্তব মূল না থাকে এবং এটি বাস্তব হয়, তবে নিউটনের পদ্ধতিটি একত্রিত হতে পারে না। যাইহোক, যদি পলিনোমিয়ালের একটি বাস্তব মূল থাকে, যা তার ডেরিভেটিভের বৃহত্তর বাস্তব মূলের চেয়ে বড় হয়, তবে নিউটনের পদ্ধতিটি চতুর্ভুজভাবে এই বৃহত্তম মূলের সাথে একত্রিত হয় যদি এই বৃহত্তর মূলের চেয়ে বড় হয় (মূলের উপরের সীমা গণনা করার সহজ উপায় রয়েছে, পলিনোমিয়াল মূলের বৈশিষ্ট্য দেখুন)। এটি মূল গণনা করার জন্য হর্নার পদ্ধতির সূচনা বিন্দু। যখন একটি মূল পাওয়া যায়, তখন পলিনোমিয়াল থেকে ফ্যাক্টর অপসারণের জন্য ইউক্লিডিয়ান বিভাগ ব্যবহার করা যেতে পারে। ফলস্বরূপ ভাগফলের একটি মূল গণনা করা এবং প্রক্রিয়াটি পুনরাবৃত্তি করা নীতিগতভাবে সমস্ত মূল গণনা করার একটি উপায় প্রদান করে। যাইহোক, এই পুনরাবৃত্তিমূলক বিন্যাসটি সংখ্যার দিক থেকে অস্থির; আনুমানিক ত্রুটিগুলি ধারাবাহিক উৎপাদককরণের সময় জমা হয়, যাতে শেষ মূলগুলি একটি বহুপদী দিয়ে নির্ধারিত হয় যা মূল বহুপদীর একটি উপাদান থেকে ব্যাপকভাবে বিচ্যুত হয়। এই ত্রুটিটি হ্রাস করার জন্য, পাওয়া প্রতিটি মূলের জন্য, নিউটনের পদ্ধতিটি মূল বহুপদী দিয়ে পুনরায় চালু করা যেতে পারে এবং এই আনুমানিক মূলটি প্রারম্ভিক মান হিসাবে। যাইহোক, কোনও নিশ্চয়তা নেই যে এটি সমস্ত শিকড় খুঁজে বের করার অনুমতি দেবে। প্রকৃতপক্ষে, তার সহগ থেকে একটি বহুপদের মূল খুঁজে বের করার সমস্যাটি অত্যন্ত অ-শর্তযুক্ত হতে পারে। এটি উইলকিনসনের বহুপদী দ্বারা চিত্রিত হয়ঃ 20 মাত্রার এই বহুপদীর মূলগুলি হল 20টি প্রথম ধনাত্মক পূর্ণসংখ্যা; তার একটি সহগের 32-বিট উপস্থাপনার শেষ বিট পরিবর্তন করলে (-210-এর সমান) মাত্র 10টি বাস্তব মূল এবং 10টি জটিল মূল সহ একটি বহুপদী তৈরি হয় যার কাল্পনিক অংশ 0.6-এর চেয়ে বড়। নিউটনের পদ্ধতির সঙ্গে হ্যালির পদ্ধতি এবং ল্যাগুয়েরের পদ্ধতি ঘনিষ্ঠভাবে সম্পর্কিত। উভয়ই একটি ঘন অভিসরণযুক্ত পুনরাবৃত্তিমূলক প্রক্রিয়ার জন্য বহুপদী এবং এর দুটি প্রথম ব্যুৎপত্তি ব্যবহার করে। এই পদ্ধতিগুলির পরপর দুটি ধাপকে একক পরীক্ষায় একত্রিত করলে, 6টি বহুপদী মূল্যায়নের (হর্নার নিয়ম সহ) ব্যয়ে 9টি অভিসারের হার পাওয়া যায়। অন্যদিকে, নিউটনের পদ্ধতির তিনটি ধাপের সংমিশ্রণে একই সংখ্যক বহুপদী মূল্যায়নের মূল্যে 8 এর অভিসারের হার পাওয়া যায়। এটি এই পদ্ধতিগুলিকে সামান্য সুবিধা দেয় (ল্যাগুয়েরের পদ্ধতির জন্য কম স্পষ্ট, কারণ প্রতিটি ধাপে একটি বর্গমূল গণনা করতে হয়)। বাস্তব সহগ এবং বাস্তব প্রারম্ভিক বিন্দু সহ বহুপদগুলিতে এই পদ্ধতিগুলি প্রয়োগ করার সময়, নিউটনের এবং হ্যালির পদ্ধতি বাস্তব সংখ্যা রেখার মধ্যে থাকে। জটিল শিকড় খুঁজে বের করার জন্য জটিল প্রারম্ভিক বিন্দুগুলি বেছে নিতে হয়। এর বিপরীতে, মূল্যায়নে বর্গমূল সহ ল্যাগুয়ের পদ্ধতিটি তার নিজস্ব সম্মতিতে আসল অক্ষটি ছেড়ে যাবে। জোড়ায় মূল খুঁজে বের করা যদি প্রদত্ত বহুপদের শুধুমাত্র বাস্তব সহগ থাকে, তাহলে কেউ জটিল সংখ্যার গণনা এড়াতে চাইতে পারে। সেই প্রভাবের জন্য, কনজুগেট জটিল শিকড়ের জোড়ার জন্য দ্বিঘাত কারণ খুঁজে বের করতে হবে। এই কাজে বহুমাত্রিক নিউটনের পদ্ধতির প্রয়োগের ফলে বেয়ারস্টোর পদ্ধতি তৈরি হয়। জেনকিন্স-ট্রব অ্যালগরিদমের আসল রূপটি এই পদ্ধতির একটি উন্নতি। সাধারণ ডুরান্ড-কার্নার এবং সামান্য জটিল অ্যাবার্থ পদ্ধতি একই সাথে শুধুমাত্র সহজ জটিল সংখ্যার গাণিতিক ব্যবহার করে সমস্ত মূল খুঁজে বের করে। দ্রুত ফুরিয়ার রূপান্তরের মতো বহু-বিন্দু মূল্যায়ন এবং ইন্টারপোলেশনের জন্য ত্বরান্বিত অ্যালগরিদমগুলি বহুপদের বড় মাত্রার জন্য তাদের গতি বাড়াতে সহায়তা করতে পারে। প্রাথমিক বিন্দুগুলির একটি অসম, কিন্তু সমানভাবে বিতরণ করা সেট বেছে নেওয়ার পরামর্শ দেওয়া হয়। মুক্ত সফ্টওয়্যার এম. পি. সলভে এই পদ্ধতির বাস্তবায়ন তার দক্ষতা এবং নির্ভুলতার জন্য একটি রেফারেন্স। এই শৈলীর আরেকটি পদ্ধতি হল ড্যানডেলিন-গ্রাফ পদ্ধতি (কখনও কখনও লোবাচেভস্কিকেও বলা হয়), যা মূলগুলিকে বারবার এবং অন্তর্নিহিতভাবে বর্গ করতে বহুপদী রূপান্তর ব্যবহার করে। এটি শিকড়ের বৈচিত্র্যকে ব্যাপকভাবে বিবর্ধিত করে। ভিয়েটের সূত্র প্রয়োগ করে, শিকড়ের মডুলাসের জন্য সহজ অনুমান পাওয়া যায়, এবং আরও কিছু প্রচেষ্টার সাথে, শিকড়গুলির জন্য। বর্জন এবং ঘের পদ্ধতি বেশ কয়েকটি দ্রুত পরীক্ষা রয়েছে যা প্রকৃত রেখার একটি অংশে বা জটিল সমতলের কোনও অঞ্চলে কোনও শিকড় নেই কিনা তা বলে। শিকড়ের মডুলাসকে আবদ্ধ করে এবং এই সীমানা দ্বারা নির্দেশিত প্রাথমিক অঞ্চলকে পুনরাবৃত্তিমূলকভাবে উপবিভাগ করে, কেউ শিকড় থাকতে পারে এমন ছোট অঞ্চলগুলিকে পৃথক করতে পারে এবং তারপরে সেগুলি সঠিকভাবে সনাক্ত করার জন্য অন্যান্য পদ্ধতি প্রয়োগ করতে পারে। এই সমস্ত পদ্ধতিতে পলিনোমিয়ালের স্থানান্তরিত এবং স্কেল করা সংস্করণগুলির সহগ খুঁজে বের করা জড়িত। বড় মাত্রায়, এফ. এফ. টি-ভিত্তিক ত্বরান্বিত পদ্ধতিগুলি কার্যকর হয়ে ওঠে। প্রকৃত শিকড়ের জন্য, পরবর্তী বিভাগগুলি দেখুন। লেহমার-শুর অ্যালগরিদম বৃত্তের জন্য শুর-কোহন পরীক্ষা ব্যবহার করে; একটি বৈকল্পিক, উইলফের বৈশ্বিক দ্বিখণ্ডন অ্যালগরিদম জটিল সমতলে আয়তক্ষেত্রাকার অঞ্চলের জন্য একটি ঘূর্ণায়মান সংখ্যা গণনা ব্যবহার করে। স্প্লিটিং সার্কেল পদ্ধতিটি এফ. এফ. টি-ভিত্তিক বহুপদী রূপান্তর ব্যবহার করে শিকড়ের গুচ্ছের সাথে সম্পর্কিত বড়-ডিগ্রি ফ্যাক্টরগুলি খুঁজে বের করে। নিউটন-টাইপ পুনরাবৃত্তি ব্যবহার করে ফ্যাক্টরাইজেশনের নির্ভুলতা সর্বাধিক করা হয়। এই পদ্ধতিটি উচ্চ মাত্রার থেকে নির্বিচারে নির্ভুলতার বহুপদগুলির মূল খুঁজে বের করার জন্য কার্যকর; এই পরিবেশে এটির প্রায় সর্বোত্তম জটিলতা রয়েছে। বাস্তব-মূল বিচ্ছিন্নতা বাস্তব সহগের সঙ্গে একটি বহুপদীর প্রকৃত শিকড় খুঁজে পাওয়া এমন একটি সমস্যা যা 19 শতকের শুরু থেকেই অনেক মনোযোগ আকর্ষণ করেছে এবং এখনও গবেষণার একটি সক্রিয় ক্ষেত্র। বেশিরভাগ মূল-সন্ধানকারী অ্যালগরিদম কিছু প্রকৃত মূল খুঁজে পেতে পারে, তবে সমস্ত মূল খুঁজে পেয়েছে বলে প্রত্যয়িত করতে পারে না। সমস্ত জটিল শিকড় খুঁজে বের করার পদ্ধতি, যেমন অ্যাবার্থ পদ্ধতি প্রকৃত শিকড় সরবরাহ করতে পারে। যাইহোক, পলিনোমিয়ালগুলির সংখ্যাসূচক অস্থিতিশীলতার কারণে (উইলকিনসনের পলিনোমিয়াল দেখুন), কোন মূলগুলি বাস্তব তা নির্ধারণের জন্য তাদের নির্বিচারে-নির্ভুল গাণিতিক প্রয়োজন হতে পারে। উপরন্তু, তারা সমস্ত জটিল মূল গণনা করে যখন মাত্র কয়েকটি বাস্তব হয়। এটি অনুসরণ করে যে বাস্তব মূলগুলি গণনা করার আদর্শ উপায় হল প্রথম বিচ্ছিন্ন ব্যবধানগুলি গণনা করা, যাকে বিচ্ছিন্ন ব্যবধান বলা হয়, যাতে প্রত্যেকটিতে ঠিক একটি বাস্তব মূল থাকে এবং তারা একসাথে সমস্ত মূল ধারণ করে। এই গণনাকে বলা হয় বাস্তব-মূল বিচ্ছিন্নতা। পৃথক ব্যবধান থাকলে, ফলাফলের নির্ভুলতার উন্নতির জন্য নিউটনের পদ্ধতির মতো দ্রুত সংখ্যাসূচক পদ্ধতি ব্যবহার করা যেতে পারে। বাস্তব-মূল বিচ্ছিন্নতার জন্য প্রাচীনতম সম্পূর্ণ অ্যালগরিদম স্টর্মের উপপাদ্য থেকে প্রাপ্ত ফলাফল। যাইহোক, এটি ডেসকার্টেসের লক্ষণের নিয়ম এবং ভিনসেন্টের উপপাদ্যের উপর ভিত্তি করে পদ্ধতিগুলির তুলনায় অনেক কম কার্যকর বলে মনে হয়। এই পদ্ধতিগুলি দুটি প্রধান শ্রেণীতে বিভক্ত, একটি অব্যাহত ভগ্নাংশ ব্যবহার করে এবং অন্যটি দ্বিখণ্ডন ব্যবহার করে। একবিংশ শতাব্দীর শুরু থেকে উভয় পদ্ধতিই নাটকীয়ভাবে উন্নত হয়েছে। এই উন্নতির মাধ্যমে তারা একটি গণনামূলক জটিলতায় পৌঁছায় যা সমস্ত মূল গণনা করার জন্য সেরা অ্যালগরিদমের অনুরূপ (এমনকি সমস্ত মূল বাস্তব হলেও)। এই অ্যালগরিদমগুলি প্রয়োগ করা হয়েছে এবং ম্যাথমেটিকা (অব্যাহত ভগ্নাংশ পদ্ধতি) এবং ম্যাপেল (দ্বিখণ্ডন পদ্ধতি)-এ উপলব্ধ। উভয় প্রয়োগই নিয়মিতভাবে 1,000 ডিগ্রির বেশি মাত্রার বহুপদের প্রকৃত মূল খুঁজে বের করতে পারে। বহুপদগুলির একাধিক শিকড় খুঁজে পাওয়া একাধিক শিকড়ের সংখ্যাসূচক গণনা একাধিক শিকড় অত্যন্ত সংবেদনশীল, যা সাধারণভাবে সংখ্যাসূচক গণনায় অ-শর্তযুক্ত এবং ভুল হিসাবে পরিচিত। ঝংগাং জেং (2004)-এর একটি পদ্ধতি, যা একটি ম্যাটল্যাব প্যাকেজ হিসাবে প্রয়োগ করা হয়েছে, সহগগুলি সঠিক না হলেও একটি বহুপদের একাধিক মূল এবং সংশ্লিষ্ট গুণিতক সঠিকভাবে গণনা করে। পদ্ধতিটি দুটি ধাপে সংক্ষিপ্ত করা যেতে পারে। প্রদত্ত পলিনোমিয়ালটি ধরা যাক। প্রথম ধাপটি একটি সংখ্যাসূচক সর্বশ্রেষ্ঠ সাধারণ বিভাজক অ্যালগরিদমের সাথে বর্গ-মুক্ত ফ্যাক্টরাইজেশন প্রয়োগ করে বহুগুণ কাঠামো নির্ধারণ করে। এটি লেখার অনুমতি দেয় যেখানে স্বতন্ত্র শিকড়ের বহুগুণ রয়েছে। এই সমীকরণটি একটি অতিরিক্ত নির্ধারিত পদ্ধতি যার সঙ্গে সহগগুলির মিলযুক্ত সমীকরণগুলিতে চলক রয়েছে (প্রধান সহগটি চলক নয়)। বেশিরভাগ ক্ষেত্রে ন্যূনতম বর্গ দ্রবণটি আর খারাপ অবস্থায় থাকে না। দ্বিতীয় ধাপটি স্বতন্ত্র মূলগুলির জন্য অতিরিক্ত নির্ধারিত সিস্টেম সমাধান করতে গাউস-নিউটন অ্যালগরিদম প্রয়োগ করে। উইলিয়াম কাহান (1972) দ্বারা আবিষ্কৃত একাধিক শিকড়ের জ্যামিতিক বৈশিষ্ট্যের কারণে একাধিক শিকড়ের সংবেদনশীলতা নিয়মিত করা যেতে পারে এবং অতিরিক্ত নির্ধারিত সিস্টেম মডেল বহুগুণ বজায় রাখে। বর্গ-মুক্ত ফ্যাক্টরাইজেশন বহুপদগুলির জন্য যার সহগগুলি সঠিকভাবে পূর্ণসংখ্যা বা মূলদ সংখ্যা হিসাবে দেওয়া হয়, তাদের এমন উপাদানগুলিতে ফ্যাক্টরাইজ করার একটি কার্যকর পদ্ধতি রয়েছে যার কেবল সহজ মূল রয়েছে এবং যার সহগগুলিও সঠিকভাবে দেওয়া হয়েছে। এই পদ্ধতি, যাকে বর্গ-মুক্ত উৎপাদককরণ বলা হয়, একটি বহুপদের একাধিক মূলের উপর ভিত্তি করে যা বহুপদের সর্বশ্রেষ্ঠ সাধারণ বিভাজকের মূল এবং তার ব্যুৎপত্তি। একটি পলিনোমিয়াল p-এর বর্গ-মুক্ত ফ্যাক্টরাইজেশন হল একটি ফ্যাক্টরাইজেশন যেখানে প্রতিটি হয় 1 বা একাধিক মূল ছাড়া একটি পলিনোমিয়াল, এবং দুটি ভিন্ন মূলের কোনও সাধারণ মূল নেই। এই ফ্যাক্টরাইজেশন গণনা করার একটি কার্যকর পদ্ধতি হল ইউন-এর অ্যালগরিদম। তথ্যসূত্র পলিনোমিয়ালস রুট-ফাইন্ডিং অ্যালগরিদম