Polynomial root-finding algorithms
کثیر الجہتی جڑوں کی تلاش ایک دیرینہ مسئلہ ہے جو پوری تاریخ میں بہت زیادہ تحقیق کا موضوع رہا ہے۔ اس کا ایک ثبوت یہ ہے کہ 19 ویں صدی تک الجبرا کا مطلب بنیادی طور پر کثیر الجہتی مساوات کا نظریہ تھا۔ اصول لکیری کثیر الجہتی (ڈگری ایک) کی جڑ تلاش کرنا آسان ہے اور اس کے لیے صرف ایک تقسیم کی ضرورت ہوتی ہے: عمومی مساوات کا حل ہوتا ہے۔ کواڈریٹک کثیر الجہتی (ڈگری دو) کے لیے، کواڈریٹک فارمولا حل پیدا کرتا ہے، لیکن اس کی عددی تشخیص کے لیے عددی استحکام کو یقینی بنانے کے لیے کچھ دیکھ بھال کی ضرورت پڑ سکتی ہے۔ ڈگری تین اور چار کے لیے، ریڈیکلز کے لحاظ سے بند شکل کے حل ہوتے ہیں، جو عام طور پر عددی تشخیص کے لیے آسان نہیں ہوتے ہیں، کیونکہ یہ بہت پیچیدہ ہوتے ہیں اور اس میں کئی جڑوں کی گنتی شامل ہوتی ہے جن کی گنتی کثیر الجہتی کے جڑوں کی براہ راست گنتی سے آسان نہیں ہوتی ہے (مثال کے طور پر کیوبک کثیر الجہتی کے حقیقی جڑوں کا اظہار غیر حقیقی مکعب جڑوں پر مشتمل ہو سکتا ہے)۔ ڈگری پانچ یا اس سے زیادہ کے کثیر الجہتی کے لیے ایبل روفینی تھیوریم اس بات پر زور دیتا ہے کہ عام طور پر جڑوں کا کوئی بنیادی اظہار نہیں ہے۔ لہذا، بہت کم ڈگریوں کے علاوہ، کثیر الجہتی کی جڑ کی تلاش جڑوں کے تخمینے تلاش کرنے پر مشتمل ہوتی ہے۔ الجبرا کے بنیادی نظریہ کے مطابق، ڈگری کے کثیر الجہتی میں بالکل حقیقی یا پیچیدہ جڑیں ہوتی ہیں جو ضرب شمار کرتی ہیں۔ اس کے بعد کثیر الجہتی کے لیے جڑ تلاش کرنے کے مسئلے کو تین مختلف ذیلی مسائل میں تقسیم کیا جا سکتا ہے۔ ایک جڑ تلاش کرنا تمام جڑوں کو تلاش کرنا پیچیدہ سطح کے ایک مخصوص علاقے میں جڑیں تلاش کرنا، عام طور پر حقیقی جڑیں یا کسی دیئے گئے وقفے میں حقیقی جڑیں (مثال کے طور پر، جب جڑیں کسی جسمانی مقدار کی نمائندگی کرتی ہیں، تو صرف حقیقی مثبت ہی دلچسپ ہوتی ہیں)۔ ایک جڑ تلاش کرنے کے لیے، نیوٹن کا طریقہ اور دیگر عمومی تکراری طریقے عام طور پر اچھی طرح سے کام کرتے ہیں۔ تمام جڑوں کو تلاش کرنے کے لیے، غالبا سب سے زیادہ قابل اعتماد طریقہ فرانسس کیو آر الگورتھم ہے جو کثیر الجہتی کے مطابق کمپینین میٹرکس کی آئجن ویلیوز کا حساب لگاتا ہے، جسے میٹ لیب میں معیاری طریقہ کے طور پر لاگو کیا جاتا ہے۔ تمام جڑوں کو تلاش کرنے کا سب سے قدیم طریقہ ایک ہی جڑ تلاش کر کے شروع کرنا ہے۔ جب کوئی جڑ مل جاتی ہے تو اسے بائنومیل کو تقسیم کر کے کثیر الجہتی سے ہٹایا جا سکتا ہے۔ نتیجے میں آنے والے کثیر الجہتی میں بقیہ جڑیں ہوتی ہیں، جو اس عمل کو دہرانے سے مل سکتی ہیں۔ تاہم، کم ڈگریوں کے علاوہ، عددی عدم استحکام کی وجہ سے یہ اچھی طرح سے کام نہیں کرتا ہے: ولکنسن کے کثیر الجہتی سے پتہ چلتا ہے کہ ایک گتانک کی بہت چھوٹی ترمیم نہ صرف جڑوں کی قدر، بلکہ ان کی نوعیت (حقیقی یا پیچیدہ) کو بھی ڈرامائی طور پر تبدیل کر سکتی ہے۔ نیز، یہاں تک کہ ایک اچھے تخمینے کے ساتھ بھی، جب کوئی ایک کثیر الجہتی کا تخمینہ لگ بھگ جڑ پر کرتا ہے، تو اسے ایسا نتیجہ مل سکتا ہے جو صفر کے قریب ہونا بہت دور ہے۔ مثال کے طور پر، اگر ڈگری 20 کی کثیر الجہتی (ولکنسن کی کثیر الجہتی کی ڈگری) کا جڑ 10 کے قریب ہے، تو جڑ پر کثیر الجہتی کا مشتق اس کی ترتیب کا ہو سکتا ہے جس سے یہ ظاہر ہوتا ہے کہ جڑ کی قیمت پر ایک غلطی تقریبا جڑ پر کثیر الجہتی کی قیمت پیدا کر سکتی ہے جو کہ ترتیب کی ہے۔ ان مسائل سے بچنے کے لیے، طریقوں کو تفصیل سے بیان کیا گیا ہے، جو بیک وقت تمام جڑوں کا حساب لگاتے ہیں، کسی بھی مطلوبہ درستگی کے لیے۔ فی الحال سب سے موثر طریقہ ایبرتھ طریقہ ہے۔ ایم پی سولیو کے نام سے ایک مفت عمل درآمد دستیاب ہے۔ یہ ایک حوالہ عمل درآمد ہے، جو معمول کے مطابق 1,000 سے بڑے ڈگری کے کثیر الجہتی کی جڑیں تلاش کر سکتا ہے، جس میں 1,000 سے زیادہ اہم اعشاریہ ہندسوں ہوتے ہیں۔ تمام جڑوں کی گنتی کے طریقے حقیقی جڑوں کی گنتی کے لیے استعمال کیے جا سکتے ہیں۔ تاہم، یہ فیصلہ کرنا مشکل ہو سکتا ہے کہ چھوٹے خیالی حصے والی جڑ حقیقی ہے یا نہیں۔ مزید برآں، چونکہ حقیقی جڑوں کی تعداد، اوسطا، ڈگری کا لوگرتھم ہے، جب کوئی حقیقی جڑوں میں دلچسپی رکھتا ہے تو غیر حقیقی جڑوں کا حساب لگانا کمپیوٹر کے وسائل کا ضیاع ہے۔ حقیقی جڑوں کی تعداد کا حساب لگانے کا سب سے قدیم طریقہ، اور وقفے میں جڑوں کی تعداد کا نتیجہ اسٹرم کے نظریہ سے نکلتا ہے، لیکن ڈیکارٹس کی علامتوں کی حکمرانی اور اس کی توسیع پر مبنی طریقے-بوڈن اور ونسنٹ کے نظریات-عام طور پر زیادہ موثر ہوتے ہیں۔ جڑوں کی تلاش کے لیے، سب ان وقفوں کے سائز کو کم کرتے ہوئے آگے بڑھتے ہیں جن میں جڑوں کی تلاش کی جاتی ہے یہاں تک کہ صفر یا ایک جڑ والے وقفے حاصل کیے جاتے ہیں۔ پھر ایک جڑ پر مشتمل وقفوں کو مزید کم کیا جا سکتا ہے تاکہ نیوٹن کے طریقہ کار کو الگ تھلگ جڑوں میں یکجا کیا جا سکے۔ اہم کمپیوٹر الجبرا سسٹمز (میپل، میتھمیٹکا، سیج میتھ، پی اے آر آئی/جی پی) میں ہر ایک میں اس طریقہ کار کی ایک قسم ہوتی ہے جو کسی کثیر الجہتی کے حقیقی جڑوں کے لیے ڈیفالٹ الگورتھم ہوتی ہے۔ طریقوں کی کلاس کثیر الجہتی جڑوں کو تلاش کرنے کے مسئلے کو کثیر الجہتی کے ساتھی میٹرکس کی آئجن ویلیوز کو تلاش کرنے کے مسئلے میں تبدیل کرنے پر مبنی ہے، اصولی طور پر، کثیر الجہتی کی جڑوں کو تلاش کرنے کے لیے کوئی بھی آئجن ویلیو الگورتھم استعمال کر سکتا ہے۔ تاہم، کارکردگی کی وجوہات کی بناء پر کوئی بھی ایسے طریقوں کو ترجیح دیتا ہے جو میٹرکس کے ڈھانچے کو استعمال کرتے ہیں، یعنی میٹرکس سے پاک شکل میں لاگو کیا جا سکتا ہے۔ ان طریقوں میں پاور کا طریقہ بھی شامل ہے، جس کا استعمال ساتھی میٹرکس کے ٹرانسپوز پر سب سے بڑے ماڈیولس کی جڑ تلاش کرنے کے لیے کلاسیکی برنولی کا طریقہ ہے۔ شفٹوں کے ساتھ الٹا طاقت کا طریقہ، جو پہلے کچھ سب سے چھوٹی جڑ ڈھونڈتا ہے، وہی ہے جو جینکنز-ٹراؤب الگورتھم کے پیچیدہ (سی پولی) قسم کو چلاتا ہے اور اسے اس کا عددی استحکام دیتا ہے۔ مزید برآں، کلسٹرڈ جڑوں کی موجودگی میں بھی اس کی ترتیب کے ساتھ تیزی سے ہم آہنگی ہوتی ہے (جہاں سنہری تناسب ہے)۔ یہ تیز کنورجنس فی مرحلہ تین کثیر الجہتی تشخیص کی لاگت کے ساتھ آتا ہے، جس کے نتیجے میں، جو کہ نیوٹن کے طریقہ کار کے تین مراحل کے مقابلے میں سست کنورجنس ہے۔ ایک جڑ تلاش کرنا جڑ کی گنتی کے لیے سب سے زیادہ استعمال ہونے والا طریقہ نیوٹن کا طریقہ ہے، جو ایک اچھی طرح سے منتخب کردہ قدر سے شروع کرتے ہوئے کی گنتی کے تکرار پر مشتمل ہوتا ہے۔ اگر ایک کثیر الجہتی ہے، تو ہر تکرار میں کثیر الجہتی اور اس کے مشتق کی گنتی کے لیے پری پروسیسنگ کے ساتھ ہورنر کا طریقہ یا تشخیص استعمال کرتے وقت گنتی تیز ہوتی ہے۔ اگرچہ کنورجنس عام طور پر کواڈریٹک ہوتی ہے، لیکن یہ بہت آہستہ آہستہ کنورج ہو سکتی ہے یا یہاں تک کہ بالکل بھی کنورج نہیں ہو سکتی۔ خاص طور پر، اگر کثیر الجہتی کا کوئی حقیقی جڑ نہیں ہے، اور وہ حقیقی ہے، تو نیوٹن کا طریقہ یکجا نہیں ہو سکتا۔ تاہم، اگر کثیر الجہتی کا حقیقی جڑ ہے، جو اس کے مشتق کے بڑے حقیقی جڑ سے بڑا ہے، تو نیوٹن کا طریقہ اس سب سے بڑے جڑ میں چوتھائی طور پر یکجا ہوتا ہے اگر اس بڑے جڑ سے بڑا ہو (جڑوں کی اوپری حد کا حساب لگانے کے آسان طریقے ہیں، کثیر الجہتی جڑوں کی خصوصیات دیکھیں)۔ یہ جڑوں کی گنتی کے لیے ہورنر طریقہ کار کا نقطہ آغاز ہے۔ جب ایک جڑ مل جاتی ہے، تو کثیر الجہتی سے عنصر کو ہٹانے کے لیے یوکلڈین ڈویژن کا استعمال کیا جا سکتا ہے۔ نتیجے کے حصص کی جڑ کا حساب لگانا، اور عمل کو دہرانا، اصولی طور پر، تمام جڑوں کا حساب لگانے کا ایک طریقہ فراہم کرتا ہے۔ تاہم، یہ تکراری اسکیم عددی طور پر غیر مستحکم ہے۔ تخمینہ کی غلطیاں مسلسل فیکٹرائزیشن کے دوران جمع ہوتی ہیں، تاکہ آخری جڑوں کا تعین ایک کثیر الجہتی کے ساتھ کیا جائے جو اصل کثیر الجہتی کے عنصر سے بڑے پیمانے پر ہٹ جاتا ہے۔ اس غلطی کو کم کرنے کے لیے، کوئی بھی پایا جانے والے ہر جڑ کے لیے، نیوٹن کے طریقہ کار کو اصل کثیر الجہتی کے ساتھ دوبارہ شروع کر سکتا ہے، اور یہ لگ بھگ جڑ ابتدائی قدر کے طور پر ہے۔ تاہم، اس بات کی کوئی ضمانت نہیں ہے کہ اس سے تمام جڑیں تلاش کرنے میں مدد ملے گی۔ درحقیقت، کسی کثیر الجہتی کی جڑیں اس کے کوفیشنٹس سے تلاش کرنے کا مسئلہ انتہائی غیر مشروط ہو سکتا ہے۔ اس کی مثال ولکنسن کے کثیر الجہتی سے ملتی ہے: ڈگری 20 کے اس کثیر الجہتی کے جڑ 20 پہلے مثبت عدد ہیں۔ اس کے ایک گتانک (-210 کے برابر) کی 32 بٹ نمائندگی کے آخری بٹ کو تبدیل کرنے سے ایک کثیر الجہتی پیدا ہوتا ہے جس میں صرف 10 حقیقی جڑیں اور 10 پیچیدہ جڑیں ہوتی ہیں جن کے خیالی حصے 0.6 سے بڑے ہوتے ہیں۔ نیوٹن کے طریقہ کار سے قریب سے متعلق ہیلی کا طریقہ اور لاگویر کا طریقہ ہے۔ دونوں ایک تکراری عمل کے لیے کثیر الجہتی اور اس کے دو پہلے مشتقات کا استعمال کرتے ہیں جس میں کیوبک کنورجنس ہوتا ہے۔ ان طریقوں کے لگاتار دو مراحل کو ایک ہی ٹیسٹ میں جوڑ کر، 6 کثیر الجہتی تشخیص (ہورنر رول کے ساتھ) کی قیمت پر، 9 کی کنورجنس کی شرح حاصل ہوتی ہے۔ دوسری طرف، نیوٹن کے طریقہ کار کے تین مراحل کو یکجا کرنے سے یکساں تعداد میں کثیر الجہتی تشخیص کی قیمت پر 8 کے ارتکاز کی شرح ملتی ہے۔ اس سے ان طریقوں کو تھوڑا سا فائدہ ملتا ہے (لاگویر کے طریقہ کار کے لیے کم واضح ہے، کیونکہ ہر مرحلے پر مربع جڑ کا حساب لگانا پڑتا ہے)۔ جب ان طریقوں کو حقیقی کوفیشنٹس اور حقیقی ابتدائی پوائنٹس کے ساتھ کثیر الجہتی پر لاگو کرتے ہیں، تو نیوٹن اور ہیلی کا طریقہ حقیقی نمبر لائن کے اندر رہتا ہے۔ پیچیدہ جڑیں تلاش کرنے کے لیے پیچیدہ ابتدائی مقامات کا انتخاب کرنا پڑتا ہے۔ اس کے برعکس، اپنی تشخیص میں مربع جڑ والا لاگویر طریقہ اپنی مرضی کے مطابق حقیقی محور کو چھوڑ دے گا۔ جوڑوں میں جڑیں تلاش کرنا اگر دی گئی کثیر الجہتی میں صرف حقیقی گتانک ہوتے ہیں، تو کوئی پیچیدہ اعداد کے ساتھ حساب سے بچنا چاہتا ہے۔ اس اثر کے لیے، کنجوگیٹ پیچیدہ جڑوں کے جوڑوں کے لیے کواڈریٹک عوامل تلاش کرنا ہوتے ہیں۔ اس کام میں کثیر جہتی نیوٹن کے طریقہ کار کے اطلاق کے نتیجے میں بیرسٹو کا طریقہ کار سامنے آتا ہے۔ جینکنز-ٹراؤب الگورتھم کی اصل شکل اس طریقہ کار میں بہتری ہے۔ تمام جڑوں کو ایک ساتھ تلاش کرنا سادہ ڈورنڈ کرنر اور قدرے زیادہ پیچیدہ ایبرتھ طریقہ بیک وقت صرف سادہ پیچیدہ نمبر ریاضی کا استعمال کرتے ہوئے تمام جڑوں کو تلاش کرتے ہیں۔ تیز فورئیر ٹرانسفارم کی طرح ملٹی پوائنٹ ایویلیوایشن اور انٹرپولیشن کے لیے تیز رفتار الگورتھم کثیر الجہتی کی بڑی ڈگریوں کے لیے ان کی رفتار بڑھانے میں مدد کر سکتے ہیں۔ یہ مشورہ دیا جاتا ہے کہ ابتدائی نکات کا ایک غیر متناسب، لیکن یکساں طور پر تقسیم شدہ سیٹ منتخب کیا جائے۔ مفت سافٹ ویئر ایم پی سولیو میں اس طریقہ کار کا نفاذ اس کی کارکردگی اور اس کی درستگی کا حوالہ ہے۔ اس انداز کا ایک اور طریقہ ڈینڈلین-گرافی طریقہ ہے (بعض اوقات لوباچوسکی سے بھی منسوب کیا جاتا ہے)، جو جڑوں کو بار بار اور واضح طور پر مربع کرنے کے لیے کثیر الجہتی تبدیلیوں کا استعمال کرتا ہے۔ یہ جڑوں میں تغیرات کو بہت بڑھاتا ہے۔ ویت کے فارمولوں کو لاگو کرتے ہوئے، جڑوں کے ماڈیولس کے لیے آسان تخمینہ حاصل ہوتا ہے، اور کچھ اور کوشش کے ساتھ، جڑوں کے لیے خود۔ اخراج اور باڑ لگانے کے طریقے کئی تیز ٹیسٹ موجود ہیں جو یہ بتاتے ہیں کہ آیا حقیقی لکیر کے کسی حصے یا پیچیدہ سطح کے کسی علاقے میں کوئی جڑیں نہیں ہیں۔ جڑوں کے ماڈیولس کو پابند کرکے اور ان حدود سے ظاہر ہونے والے ابتدائی خطے کو بار بار ذیلی تقسیم کرکے، کوئی بھی چھوٹے علاقوں کو الگ کر سکتا ہے جن میں جڑیں ہو سکتی ہیں اور پھر ان کا صحیح پتہ لگانے کے لیے دوسرے طریقے استعمال کر سکتا ہے۔ ان تمام طریقوں میں کثیر الجہتی کے منتقل شدہ اور اسکیل شدہ ورژن کے کوفیشنٹس کو تلاش کرنا شامل ہے۔ بڑی ڈگریوں کے لیے، ایف ایف ٹی پر مبنی تیز رفتار طریقے قابل عمل ہو جاتے ہیں۔ حقیقی جڑوں کے لیے، اگلے حصے دیکھیں۔ لیمر-شور الگورتھم حلقوں کے لیے شور-کون ٹیسٹ کا استعمال کرتا ہے۔ ایک قسم، ولف کا عالمی بائیسیکشن الگورتھم پیچیدہ سطح میں آئتاکار علاقوں کے لیے گھومنے والے نمبر کی گنتی کا استعمال کرتا ہے۔ تقسیم دائرے کا طریقہ جڑوں کے کلسٹرز سے مطابقت رکھنے والے بڑے درجے کے عوامل کو تلاش کرنے کے لیے ایف ایف ٹی پر مبنی کثیر الجہتی تبدیلیوں کا استعمال کرتا ہے۔ نیوٹن قسم کی تکرار کا استعمال کرتے ہوئے فیکٹرائزیشن کی درستگی کو زیادہ سے زیادہ کیا جاتا ہے۔ یہ طریقہ اعلی درجے سے لے کر صوابدیدی درستگی تک کے کثیر الجہتی کی جڑوں کو تلاش کرنے کے لیے مفید ہے۔ اس ترتیب میں اس کی تقریبا زیادہ سے زیادہ پیچیدگی ہے۔ حقیقی جڑ کی علیحدگی حقیقی کوفیشنٹس کے ساتھ کثیر الجہتی کی حقیقی جڑیں تلاش کرنا ایک ایسا مسئلہ ہے جس نے 19 ویں صدی کے آغاز سے ہی بہت توجہ حاصل کی ہے، اور اب بھی تحقیق کا ایک فعال ڈومین ہے۔ زیادہ تر جڑ تلاش کرنے والے الگورتھم کچھ حقیقی جڑیں تلاش کر سکتے ہیں، لیکن تمام جڑیں ملنے کی تصدیق نہیں کر سکتے۔ تمام پیچیدہ جڑوں کو تلاش کرنے کے طریقے، جیسے ایبرتھ طریقہ حقیقی جڑیں فراہم کر سکتا ہے۔ تاہم، کثیر الجہتی کے عددی عدم استحکام کی وجہ سے (ولکنسن کا کثیر الجہتی دیکھیں)، انہیں یہ فیصلہ کرنے کے لیے صوابدیدی صحت سے متعلق ریاضی کی ضرورت پڑ سکتی ہے کہ کون سی جڑیں حقیقی ہیں۔ مزید برآں، وہ تمام پیچیدہ جڑوں کا حساب لگاتے ہیں جب کہ صرف چند ہی حقیقی ہوتے ہیں۔ اس کے بعد حقیقی جڑوں کی گنتی کا معیاری طریقہ یہ ہے کہ پہلے جداگانہ وقفوں کی گنتی کی جائے، جنہیں الگ تھلگ وقفے کہا جاتا ہے، جیسے کہ ہر ایک بالکل ایک حقیقی جڑ پر مشتمل ہو، اور وہ مل کر تمام جڑوں پر مشتمل ہوں۔ اس حساب کو حقیقی جڑ کی تنہائی کہا جاتا ہے۔ وقفہ الگ کرنے کے بعد، کوئی بھی تیز عددی طریقے استعمال کر سکتا ہے، جیسے کہ نتیجہ کی درستگی کو بہتر بنانے کے لیے نیوٹن کا طریقہ۔ حقیقی جڑ کی تنہائی کے لیے سب سے قدیم مکمل الگورتھم اسٹرم تھیوریم کا نتیجہ ہے۔ تاہم، ایسا لگتا ہے کہ یہ ڈیکارٹس کی علامتوں کی حکمرانی اور ونسنٹ کے نظریہ پر مبنی طریقوں کے مقابلے میں بہت کم موثر ہے۔ یہ طریقے دو اہم کلاسوں میں تقسیم ہوتے ہیں، ایک مسلسل حصوں کا استعمال کرتے ہوئے اور دوسرا بائیسیکشن کا استعمال کرتے ہوئے۔ اکیسویں صدی کے آغاز سے دونوں طریقوں میں ڈرامائی طور پر بہتری آئی ہے۔ ان بہتریوں کے ساتھ وہ ایک کمپیوٹیشنل پیچیدگی تک پہنچ جاتے ہیں جو تمام جڑوں کی کمپیوٹنگ کے لیے بہترین الگورتھم سے ملتا جلتا ہے (یہاں تک کہ جب تمام جڑیں حقیقی ہوں)۔ یہ الگورتھم لاگو کیے گئے ہیں اور ریاضی (مسلسل فریکشن طریقہ) اور میپل (بائیسیکشن طریقہ) میں دستیاب ہیں۔ دونوں نفاذ معمول کے مطابق 1,000 سے زیادہ ڈگری کے کثیر الجہتی کے حقیقی جڑوں کو تلاش کر سکتے ہیں۔ کثیر الجہتی کی متعدد جڑیں تلاش کرنا متعدد جڑوں کی عددی گنتی متعدد جڑیں انتہائی حساس ہوتی ہیں، جو عام طور پر عددی گنتی میں غیر مشروط اور غلط ہونے کے لیے جانی جاتی ہیں۔ ژونگ گینگ زینگ (2004) کا ایک طریقہ، جسے MATLAB پیکیج کے طور پر لاگو کیا گیا ہے، کثیر الجہتی کے متعدد جڑوں اور متعلقہ ضرب کا درست طریقے سے حساب لگاتا ہے یہاں تک کہ اگر کوفیشنٹس غیر درست ہوں۔ طریقہ کار کا خلاصہ دو مراحل میں کیا جا سکتا ہے۔ فرض کریں کہ یہ دی گئی کثیر الجہتی ہے۔ پہلا مرحلہ عددی سب سے بڑے مشترکہ تقسیم کار الگورتھم کے ساتھ مربع فری فیکٹرائزیشن کا اطلاق کرکے ضرب کے ڈھانچے کا تعین کرتا ہے۔ یہ لکھنے کی اجازت دیتا ہے کہ مختلف جڑوں کی ضرب کہاں ہے۔ یہ مساوات ایک حد سے زیادہ طے شدہ نظام ہے جس میں مساوات پر متغیرات کوفیشنٹس سے ملاتے ہیں (لیڈنگ کوفیشنٹ متغیر نہیں ہے)۔ زیادہ تر معاملات میں سب سے کم مربع محلول اب غیر مشروط نہیں ہے۔ دوسرا مرحلہ مختلف جڑوں کے لیے حد سے زیادہ طے شدہ نظام کو حل کرنے کے لیے گاؤس-نیوٹن الگورتھم کا اطلاق کرتا ہے۔ ولیم کہان (1972) کے ذریعہ دریافت کردہ متعدد جڑوں کی ہندسی خاصیت کی وجہ سے متعدد جڑوں کی حساسیت کو باقاعدہ بنایا جا سکتا ہے اور حد سے زیادہ طے شدہ نظام ماڈل ضرب کو برقرار رکھتا ہے۔ مربع فری فیکٹرائزیشن ان کثیر الجہتی کے لیے جن کے کوفشنٹس کو بالکل انٹیجرز یا عقلی اعداد کے طور پر دیا جاتا ہے، انہیں ان عوامل میں فیکٹرائز کرنے کا ایک موثر طریقہ ہے جن کے صرف سادہ جڑ ہوتے ہیں اور جن کے کوفشنٹس بھی بالکل دیے جاتے ہیں۔ یہ طریقہ، جسے مربع فری فیکٹرائزیشن کہا جاتا ہے، کثیر الجہتی کے متعدد جڑوں پر مبنی ہے جو کثیر الجہتی اور اس کے مشتق کے سب سے بڑے مشترکہ تقسیم کار کی جڑیں ہیں۔ کثیر الجہتی p کی مربع فری فیکٹرائزیشن ایک فیکٹرائزیشن ہے جہاں ہر ایک یا تو 1 ہے یا متعدد جڑوں کے بغیر کثیر الجہتی ہے، اور دو مختلف میں کوئی مشترکہ جڑ نہیں ہے۔ اس فیکٹرائزیشن کا حساب لگانے کا ایک موثر طریقہ یون کا الگورتھم ہے۔ حوالہ جات کثیر الجہتی جڑ تلاش کرنے والے الگورتھم