Polynomial root-finding algorithms
બહુપદી મૂળ શોધવું એ લાંબા સમયથી ચાલતી સમસ્યા છે જે સમગ્ર ઇતિહાસમાં ઘણા સંશોધનનો વિષય રહી છે. આનો પુરાવો એ છે કે 19મી સદી સુધી, બીજગણિતનો અર્થ અનિવાર્યપણે બહુપદી સમીકરણોના સિદ્ધાંત હતો. સિદ્ધાંતો રેખીય બહુપદી (ડિગ્રી એક) નું મૂળ શોધવું સરળ છે અને તેને માત્ર એક જ વિભાજનની જરૂર છેઃ સામાન્ય સમીકરણનો ઉકેલ હોય છે. ડિગ્રી ત્રણ અને ચાર માટે, રેડિકલની દ્રષ્ટિએ બંધ-સ્વરૂપના ઉકેલો છે, જે સામાન્ય રીતે આંકડાકીય મૂલ્યાંકન માટે અનુકૂળ નથી, કારણ કે તે ખૂબ જ જટિલ છે અને તેમાં ઘણા મૂળની ગણતરી સામેલ છે, જેની ગણતરી બહુપદીના મૂળની સીધી ગણતરી કરતાં સરળ નથી (ઉદાહરણ તરીકે ઘન બહુપદીના વાસ્તવિક મૂળની અભિવ્યક્તિમાં બિન-વાસ્તવિક સમઘન મૂળનો સમાવેશ થઈ શકે છે). ડિગ્રી પાંચ અથવા તેનાથી વધુની બહુપદીઓ માટે એબેલ-રફિની પ્રમેય ભારપૂર્વક જણાવે છે કે, સામાન્ય રીતે, મૂળની કોઈ આમૂલ અભિવ્યક્તિ નથી. તેથી, ખૂબ ઓછી ડિગ્રી સિવાય, બહુપદીઓના મૂળ શોધમાં મૂળના અંદાજો શોધવાનો સમાવેશ થાય છે. બીજગણિતના મૂળભૂત પ્રમેય અનુસાર, ડિગ્રીની બહુપદી બરાબર વાસ્તવિક અથવા જટિલ મૂળ ધરાવે છે જે ગુણાકારની ગણતરી કરે છે. તે અનુસરે છે કે બહુપદીઓ માટે મૂળ શોધવાની સમસ્યાને ત્રણ જુદી જુદી પેટા સમસ્યાઓમાં વિભાજિત કરી શકાય છે; એક મૂળ શોધવું બધા મૂળ શોધવું જટિલ સમતલના ચોક્કસ પ્રદેશમાં મૂળ શોધવું, સામાન્ય રીતે વાસ્તવિક મૂળ અથવા આપેલ અંતરાલમાં વાસ્તવિક મૂળ શોધવું (ઉદાહરણ તરીકે, જ્યારે મૂળ ભૌતિક જથ્થાને રજૂ કરે છે, ત્યારે માત્ર વાસ્તવિક હકારાત્મક જ રસપ્રદ હોય છે). એક મૂળ શોધવા માટે, ન્યૂટનની પદ્ધતિ અને અન્ય સામાન્ય પુનરાવર્તિત પદ્ધતિઓ સામાન્ય રીતે સારી રીતે કામ કરે છે. તમામ મૂળ શોધવા માટે, દલીલપૂર્વક સૌથી વિશ્વસનીય પદ્ધતિ ફ્રાન્સિસ ક્યૂ. આર. અલ્ગોરિધમ છે જે બહુપદીને અનુરૂપ કમ્પેનિયન મેટ્રિક્સના આઈગનવેલ્યુની ગણતરી કરે છે, જે MATLAB માં પ્રમાણભૂત પદ્ધતિ તરીકે લાગુ કરવામાં આવે છે. તમામ મૂળ શોધવાની સૌથી જૂની પદ્ધતિ એ છે કે એક જ મૂળ શોધવાની શરૂઆત કરવી. જ્યારે મૂળ મળી આવે છે, ત્યારે તેને દ્વિપદીને વિભાજીત કરીને બહુપદીમાંથી દૂર કરી શકાય છે. પરિણામી બહુપદીમાં બાકીના મૂળ હોય છે, જે આ પ્રક્રિયા પર પુનરાવર્તન કરીને શોધી શકાય છે. જો કે, ઓછી ડિગ્રી સિવાય, આંકડાકીય અસ્થિરતાને કારણે આ સારી રીતે કામ કરતું નથીઃ વિલ્કિન્સનની બહુપદી દર્શાવે છે કે એક ગુણાંકનો ખૂબ જ નાનો ફેરફાર માત્ર મૂળના મૂલ્યમાં જ નહીં, પણ તેમની પ્રકૃતિ (વાસ્તવિક અથવા જટિલ) માં પણ નાટકીય રીતે ફેરફાર કરી શકે છે. ઉપરાંત, સારા અંદાજ સાથે પણ, જ્યારે કોઈ બહુપદીનું અંદાજિત મૂળ પર મૂલ્યાંકન કરે છે, ત્યારે તેને એવું પરિણામ મળી શકે છે જે શૂન્યની નજીક છે. ઉદાહરણ તરીકે, જો ડિગ્રી 20 ની બહુપદી (વિલ્કિન્સનની બહુપદીની ડિગ્રી) નું મૂળ 10 ની નજીક હોય, તો મૂળ પર બહુપદીનું વ્યુત્પન્ન આના ક્રમમાં હોઈ શકે છે જે સૂચવે છે કે મૂળના મૂલ્ય પરની ભૂલ બહુપદીનું મૂલ્ય અંદાજિત મૂળ પર ઉત્પન્ન કરી શકે છે જે ક્રમમાં છે. હાલમાં સૌથી કાર્યક્ષમ પદ્ધતિ એબરથ પદ્ધતિ છે. એમ. પી. સોલ્વના નામ હેઠળ મફત અમલીકરણ ઉપલબ્ધ છે. આ એક સંદર્ભ અમલીકરણ છે, જે 1,000 થી વધુ નોંધપાત્ર દશાંશ અંકો સાથે 1,000 થી વધુ ડિગ્રીની બહુપદીઓના મૂળ નિયમિતપણે શોધી શકે છે. તમામ મૂળની ગણતરી કરવાની પદ્ધતિઓનો ઉપયોગ વાસ્તવિક મૂળની ગણતરી માટે થઈ શકે છે. જો કે, તે નક્કી કરવું મુશ્કેલ હોઈ શકે છે કે નાના કાલ્પનિક ભાગ સાથેનું મૂળ વાસ્તવિક છે કે નહીં. વધુમાં, વાસ્તવિક મૂળની સંખ્યા સરેરાશ ડિગ્રીનો લઘુગણક હોવાથી, જ્યારે કોઈને વાસ્તવિક મૂળમાં રસ હોય ત્યારે બિન-વાસ્તવિક મૂળની ગણતરી કરવી એ કમ્પ્યુટર સંસાધનોનો બગાડ છે. વાસ્તવિક મૂળની સંખ્યા અને અંતરાલમાં મૂળની સંખ્યાની ગણતરી કરવાની સૌથી જૂની પદ્ધતિ સ્ટર્મના પ્રમેયમાંથી પરિણમે છે, પરંતુ ડેસકાર્ટેસના સંકેતોના નિયમ અને તેના વિસ્તરણ પર આધારિત પદ્ધતિઓ-બુડન અને વિન્સેન્ટના પ્રમેયો-સામાન્ય રીતે વધુ કાર્યક્ષમ છે. મૂળ શોધવા માટે, બધા શૂન્ય અથવા એક મૂળ ધરાવતા અંતરાલો ન મળે ત્યાં સુધી અંતરાલોના કદને ઘટાડીને આગળ વધે છે જેમાં મૂળ શોધવામાં આવે છે. પછી એક મૂળ ધરાવતા અંતરાલોને ન્યુટનની પદ્ધતિનું અલગ મૂળમાં દ્વિઘાત અભિસરણ મેળવવા માટે વધુ ઘટાડી શકાય છે. મુખ્ય કોમ્પ્યુટર બીજગણિત પ્રણાલીઓ (મેપલ, મેથેમેટિકા, સેજમેથ, પી. એ. આર. આઈ./જી. પી.) બહુપદીના વાસ્તવિક મૂળ માટે મૂળભૂત અલ્ગોરિધમ તરીકે આ પદ્ધતિનો એક પ્રકાર ધરાવે છે. પદ્ધતિઓનો વર્ગ બહુપદીના મૂળ શોધવાની સમસ્યાને બહુપદીના સાથી મેટ્રિક્સના આઈગનવેલ્યુ શોધવાની સમસ્યામાં રૂપાંતરિત કરવા પર આધારિત છે, સિદ્ધાંતમાં, બહુપદીના મૂળ શોધવા માટે કોઈપણ આઈગનવેલ્યુ અલ્ગોરિધમનો ઉપયોગ કરી શકે છે. જો કે, કાર્યક્ષમતાના કારણોસર વ્યક્તિ એવી પદ્ધતિઓ પસંદ કરે છે જે મેટ્રિક્સની રચનાનો ઉપયોગ કરે છે, એટલે કે, મેટ્રિક્સ-મુક્ત સ્વરૂપમાં અમલ કરી શકાય છે. આ પદ્ધતિઓમાં પાવર પદ્ધતિ છે, જેનો કમ્પેનિયન મેટ્રિક્સના ટ્રાન્સપોઝ પર ઉપયોગ એ ગ્રેટેસ્ટ મોડ્યુલસનું મૂળ શોધવા માટેની ક્લાસિકલ બર્નૌલીની પદ્ધતિ છે. શિફ્ટ સાથેની ઇન્વર્સ પાવર પદ્ધતિ, જે પહેલા કેટલાક નાના મૂળ શોધે છે, તે જેનકિન્સ-ટ્રોબ અલ્ગોરિધમનો જટિલ (સી. પી. ઓ. એલ.) પ્રકાર ચલાવે છે અને તેને તેની આંકડાકીય સ્થિરતા આપે છે. વધુમાં, તે ક્લસ્ટર્ડ મૂળની હાજરીમાં પણ ક્રમ સાથે ઝડપી અભિસરણ ધરાવે છે (જ્યાં સુવર્ણ ગુણોત્તર છે). આ ઝડપી અભિસરણ દરેક પગલા દીઠ ત્રણ બહુપદી મૂલ્યાંકનની કિંમત સાથે આવે છે, જેના પરિણામે અવશેષ આવે છે, જે ન્યૂટનની પદ્ધતિના ત્રણ પગલાઓની સરખામણીમાં ધીમું અભિસરણ છે. એક મૂળ શોધવું રુટની ગણતરી માટે સૌથી વધુ ઉપયોગમાં લેવાતી પદ્ધતિ એ ન્યૂટનની પદ્ધતિ છે, જેમાં સારી રીતે પસંદ કરેલા મૂલ્યથી શરૂ કરીને ગણતરીના પુનરાવર્તનનો સમાવેશ થાય છે જો બહુપદી હોય, તો દરેક પુનરાવર્તનમાં બહુપદી અને તેના વ્યુત્પન્નની ગણતરી માટે પૂર્વપ્રક્રિયા સાથે હોર્નરની પદ્ધતિ અથવા મૂલ્યાંકનનો ઉપયોગ કરતી વખતે ગણતરી ઝડપી હોય છે. તેમ છતાં કન્વર્જન્સ સામાન્ય રીતે દ્વિઘાત હોય છે, તે ખૂબ ધીમેથી કન્વર્જ થઈ શકે છે અથવા તો બિલકુલ કન્વર્જ ન પણ થઈ શકે. ખાસ કરીને, જો બહુપદીનું કોઈ વાસ્તવિક મૂળ ન હોય અને તે વાસ્તવિક હોય, તો ન્યૂટનની પદ્ધતિ એકરૂપ થઈ શકતી નથી. જો કે, જો બહુપદીમાં વાસ્તવિક મૂળ હોય, જે તેના વ્યુત્પન્નના મોટા વાસ્તવિક મૂળ કરતાં મોટું હોય, તો ન્યુટનની પદ્ધતિ આ મોટા મૂળ કરતાં મોટી હોય તો આ સૌથી મોટા મૂળમાં ચતુર્ભુજ રીતે એકરૂપ થાય છે (મૂળની ઉપરની મર્યાદાની ગણતરી કરવાની સરળ રીતો છે, બહુપદી મૂળના ગુણધર્મો જુઓ). મૂળની ગણતરી કરવા માટે હોર્નર પદ્ધતિનો આ પ્રારંભિક બિંદુ છે. જ્યારે એક મૂળ મળી આવે છે, ત્યારે બહુપદીમાંથી પરિબળને દૂર કરવા માટે યુક્લિડિયન વિભાજનનો ઉપયોગ કરી શકાય છે. પરિણામી ભાગાકારના મૂળની ગણતરી કરવી અને પ્રક્રિયાને પુનરાવર્તિત કરવી, સૈદ્ધાંતિક રીતે, તમામ મૂળની ગણતરી કરવાની રીત પૂરી પાડે છે. જો કે, આ પુનરાવર્તિત યોજના આંકડાકીય રીતે અસ્થિર છે; અંદાજિત ભૂલો ક્રમિક ફેક્ટરાઇઝેશન દરમિયાન એકઠી થાય છે, જેથી છેલ્લા મૂળ બહુપદી સાથે નક્કી થાય છે જે મૂળ બહુપદીના પરિબળથી વ્યાપકપણે વિચલિત થાય છે. આ ભૂલને ઘટાડવા માટે, દરેક મૂળ જે મળી આવે છે તેના માટે, મૂળ બહુપદી સાથે ન્યૂટનની પદ્ધતિને પુનઃપ્રારંભ કરી શકાય છે, અને આ અંદાજિત મૂળ પ્રારંભિક મૂલ્ય તરીકે. જો કે, એવી કોઈ બાંયધરી નથી કે આ તમામ મૂળ શોધવાની મંજૂરી આપશે. હકીકતમાં, બહુપદીના મૂળને તેના ગુણાંકમાંથી શોધવાની સમસ્યા અત્યંત અયોગ્ય હોઈ શકે છે. આ વિલ્કિન્સનની બહુપદી દ્વારા સચિત્ર છેઃ 20 ડિગ્રીની આ બહુપદીના મૂળ 20 પ્રથમ હકારાત્મક પૂર્ણાંકો છે; તેના એક ગુણાંક (-210 ની બરાબર) ની 32-બીટ રજૂઆતના છેલ્લા બીટને બદલીને માત્ર 10 વાસ્તવિક મૂળ અને 10 જટિલ મૂળ સાથે બહુપદી ઉત્પન્ન થાય છે, જેમાં કાલ્પનિક ભાગો 0.6 કરતા મોટા હોય છે. ન્યૂટનની પદ્ધતિ સાથે હેલીની પદ્ધતિ અને લાગ્યુરેની પદ્ધતિ નજીકથી સંબંધિત છે. બંને ક્યુબિક કન્વર્જન્સ ધરાવતી પુનરાવર્તિત પ્રક્રિયા માટે બહુપદી અને તેના બે પ્રથમ વ્યુત્પત્તિઓનો ઉપયોગ કરે છે. આ પદ્ધતિઓના સતત બે પગલાંને એક જ પરીક્ષણમાં જોડીને, 6 બહુપદી મૂલ્યાંકન (હોર્નર નિયમ સાથે) ની કિંમત પર 9નો અભિસરણ દર મળે છે. બીજી બાજુ, ન્યૂટનની પદ્ધતિના ત્રણ પગલાંઓનું સંયોજન બહુપદી મૂલ્યાંકનની સમાન સંખ્યાના ખર્ચે 8ના અભિસરણનો દર આપે છે. આ આ પદ્ધતિઓને થોડો ફાયદો આપે છે (લેગ્યુરેની પદ્ધતિ માટે ઓછી સ્પષ્ટ છે, કારણ કે દરેક પગલામાં વર્ગમૂળની ગણતરી કરવી પડે છે). વાસ્તવિક ગુણાંક અને વાસ્તવિક પ્રારંભિક બિંદુઓ સાથેની બહુપદીઓ પર આ પદ્ધતિઓ લાગુ કરતી વખતે, ન્યૂટન અને હેલીની પદ્ધતિ વાસ્તવિક સંખ્યા રેખાની અંદર રહે છે. જટિલ મૂળ શોધવા માટે જટિલ પ્રારંભિક બિંદુઓ પસંદ કરવા પડે છે. તેનાથી વિપરીત, તેના મૂલ્યાંકનમાં વર્ગમૂળ ધરાવતી લેગુએરે પદ્ધતિ તેના પોતાના અનુસાર વાસ્તવિક અક્ષને છોડી દેશે. જો આપેલ બહુપદીમાં માત્ર વાસ્તવિક ગુણાંક હોય, તો કોઈ વ્યક્તિ જટિલ સંખ્યાઓ સાથેની ગણતરીઓ ટાળવા માંગે છે. તે અસર માટે, સંયુગ્મિત જટિલ મૂળની જોડી માટે દ્વિઘાત પરિબળો શોધવા પડશે. આ કાર્ય માટે બહુ-પરિમાણીય ન્યૂટનની પદ્ધતિનો ઉપયોગ બેયરસ્ટોની પદ્ધતિમાં પરિણમે છે. જેનકિન્સ-ટ્રોબ અલ્ગોરિધમનો વાસ્તવિક પ્રકાર આ પદ્ધતિનો સુધારો છે. સરળ ડુરાન્ડ-કર્નર અને થોડી વધુ જટિલ એબરથ પદ્ધતિ એક સાથે માત્ર સરળ જટિલ સંખ્યાના અંકગણિતનો ઉપયોગ કરીને તમામ મૂળ શોધે છે. બહુ-બિંદુ મૂલ્યાંકન અને ઝડપી ફોરિયર ટ્રાન્સફોર્મ જેવા અંતર્વેશન માટે ત્વરિત અલ્ગોરિધમ્સ બહુપદીના મોટા પ્રમાણ માટે તેમને ઝડપી બનાવવામાં મદદ કરી શકે છે. અસમપ્રમાણતાવાળા, પરંતુ સમાનરૂપે વહેંચાયેલા પ્રારંભિક બિંદુઓના સમૂહને પસંદ કરવાની સલાહ આપવામાં આવે છે. મુક્ત સોફ્ટવેર એમ. પી. સોલ્વમાં આ પદ્ધતિનો અમલ તેની કાર્યક્ષમતા અને તેની ચોકસાઈ માટેનો સંદર્ભ છે. આ શૈલી સાથેની બીજી પદ્ધતિ ડેન્ડેલિન-ગ્રેફ પદ્ધતિ છે (કેટલીકવાર લોબાચેવસ્કી તરીકે પણ ઓળખાય છે), જે મૂળને વારંવાર અને પરોક્ષ રીતે ચોરસ કરવા માટે બહુપદી પરિવર્તનોનો ઉપયોગ કરે છે. આ મૂળમાં તફાવતોને મોટા પ્રમાણમાં વધારે છે. વિએટના સૂત્રોને લાગુ કરીને, મૂળના મોડ્યુલસ માટે સરળ અંદાજો મેળવવામાં આવે છે, અને થોડા વધુ પ્રયત્નો સાથે, મૂળ માટે જ. બાકાત અને આવરણ પદ્ધતિઓ કેટલાક ઝડપી પરીક્ષણો અસ્તિત્વ ધરાવે છે જે દર્શાવે છે કે વાસ્તવિક રેખાના કોઈ ભાગમાં અથવા જટિલ સમતલના પ્રદેશમાં કોઈ મૂળ નથી. મૂળના મોડ્યુલસને બાંધીને અને આ સીમાઓ દ્વારા દર્શાવેલ પ્રારંભિક પ્રદેશને પુનરાવર્તિત રીતે પેટા વિભાજિત કરીને, કોઈ પણ વ્યક્તિ નાના પ્રદેશોને અલગ કરી શકે છે જેમાં મૂળ હોઈ શકે છે અને પછી તેમને બરાબર સ્થિત કરવા માટે અન્ય પદ્ધતિઓ લાગુ કરી શકે છે. આ તમામ પદ્ધતિઓમાં બહુપદીની સ્થાનાંતરિત અને સ્કેલ કરેલી આવૃત્તિઓના ગુણાંક શોધવાનો સમાવેશ થાય છે. મોટા પ્રમાણ માટે, એફ. એફ. ટી. આધારિત પ્રવેગક પદ્ધતિઓ વ્યવહારુ બને છે. વાસ્તવિક મૂળ માટે, આગામી વિભાગો જુઓ. લેહમર-શુર અલ્ગોરિધમ વર્તુળો માટે શુર-કોહ્ન પરીક્ષણનો ઉપયોગ કરે છે; એક પ્રકાર, વિલ્ફનું વૈશ્વિક દ્વિભાજન અલ્ગોરિધમ જટિલ સમતલમાં લંબચોરસ પ્રદેશો માટે વળાંક સંખ્યા ગણતરીનો ઉપયોગ કરે છે. વિભાજન વર્તુળ પદ્ધતિ મૂળના સમૂહને અનુરૂપ મોટા-ડિગ્રી પરિબળો શોધવા માટે એફ. એફ. ટી. આધારિત બહુપદી પરિવર્તનોનો ઉપયોગ કરે છે. ન્યુટન-પ્રકારના પુનરાવર્તનનો ઉપયોગ કરીને ફેક્ટરાઇઝેશનની ચોકસાઈ મહત્તમ કરવામાં આવે છે. આ પદ્ધતિ ઉચ્ચ ડિગ્રીથી મનસ્વી ચોકસાઇની બહુપદીઓના મૂળ શોધવા માટે ઉપયોગી છે; આ સેટિંગમાં તે લગભગ શ્રેષ્ઠ જટિલતા ધરાવે છે. વાસ્તવિક મૂળ અલગતા વાસ્તવિક ગુણાંક સાથે બહુપદીના વાસ્તવિક મૂળ શોધવી એ એક એવી સમસ્યા છે જેણે 19મી સદીની શરૂઆતથી ઘણું ધ્યાન ખેંચ્યું છે, અને તે હજુ પણ સંશોધનનું સક્રિય ક્ષેત્ર છે. મોટાભાગના મૂળ શોધવાના અલ્ગોરિધમ્સ કેટલાક વાસ્તવિક મૂળ શોધી શકે છે, પરંતુ તમામ મૂળ મળ્યાં હોવાનું પ્રમાણિત કરી શકતા નથી. તમામ જટિલ મૂળ શોધવા માટેની પદ્ધતિઓ, જેમ કે એબરથ પદ્ધતિ વાસ્તવિક મૂળ પ્રદાન કરી શકે છે. જો કે, બહુપદીઓની આંકડાકીય અસ્થિરતાને કારણે (વિલ્કિન્સનની બહુપદી જુઓ), તેમને કયા મૂળ વાસ્તવિક છે તે નક્કી કરવા માટે મનસ્વી-ચોકસાઇ અંકગણિતની જરૂર પડી શકે છે. વધુમાં, જ્યારે માત્ર થોડા જ વાસ્તવિક હોય ત્યારે તેઓ તમામ જટિલ મૂળની ગણતરી કરે છે. તે અનુસરે છે કે વાસ્તવિક મૂળની ગણતરી કરવાની પ્રમાણભૂત રીત એ છે કે પ્રથમ અસંબદ્ધ અંતરાલોની ગણતરી કરવી, જેને અલગ અંતરાલો કહેવાય છે, જેમ કે દરેકમાં બરાબર એક વાસ્તવિક મૂળ હોય છે, અને એકસાથે તેઓ તમામ મૂળ ધરાવે છે. આ ગણતરીને વાસ્તવિક મૂળ અલગતા કહેવામાં આવે છે. અલગ અંતરાલ સાથે, કોઈ ઝડપી આંકડાકીય પદ્ધતિઓનો ઉપયોગ કરી શકે છે, જેમ કે પરિણામની ચોકસાઈ સુધારવા માટે ન્યૂટનની પદ્ધતિ. વાસ્તવિક મૂળના અલગતા માટેનું સૌથી જૂનું સંપૂર્ણ અલ્ગોરિધમ સ્ટર્મના પ્રમેયમાંથી પરિણમે છે. જો કે, તે ડેસકાર્ટેસના સંકેતોના નિયમ અને વિન્સેન્ટના પ્રમેય પર આધારિત પદ્ધતિઓ કરતાં ઘણી ઓછી કાર્યક્ષમ હોવાનું જણાય છે. આ પદ્ધતિઓ બે મુખ્ય વર્ગોમાં વહેંચાયેલી છે, એક સતત અપૂર્ણાંકનો ઉપયોગ કરીને અને બીજી દ્વિભાજનનો ઉપયોગ કરીને. 21મી સદીની શરૂઆતથી બંને પદ્ધતિઓમાં નાટ્યાત્મક સુધારો થયો છે. આ સુધારાઓ સાથે તેઓ ગણતરીની જટિલતા સુધી પહોંચે છે જે તમામ મૂળની ગણતરી માટે શ્રેષ્ઠ અલ્ગોરિધમ્સ જેવી જ છે (ભલે તમામ મૂળ વાસ્તવિક હોય). આ અલ્ગોરિધમ્સ અમલમાં મૂકવામાં આવ્યા છે અને ગણિત (સતત અપૂર્ણાંક પદ્ધતિ) અને મેપલ (દ્વિભાજન પદ્ધતિ) માં ઉપલબ્ધ છે. બંને અમલીકરણ નિયમિતપણે 1,000 કરતા વધુ ડિગ્રીની બહુપદીઓના વાસ્તવિક મૂળ શોધી શકે છે. બહુપદીઓના બહુવિધ મૂળ શોધવું બહુવિધ મૂળની આંકડાકીય ગણતરી બહુવિધ મૂળ અત્યંત સંવેદનશીલ હોય છે, જે સામાન્ય રીતે આંકડાકીય ગણતરીમાં અયોગ્ય અને અચોક્કસ હોવાનું જાણીતું છે. ઝોંગગેંગ ઝેંગ (2004) દ્વારા MATLAB પેકેજ તરીકે અમલમાં મુકવામાં આવેલી પદ્ધતિ, ગુણાંક અચોક્કસ હોવા છતાં પણ બહુપદીના બહુવિધ મૂળ અને અનુરૂપ ગુણાકારની ચોક્કસ ગણતરી કરે છે. આ પદ્ધતિનો સારાંશ બે તબક્કામાં આપી શકાય છે. આપેલ બહુપદી દો. પ્રથમ પગલું આંકડાકીય સૌથી મોટા સામાન્ય વિભાજક અલ્ગોરિધમ સાથે વર્ગ-મુક્ત ગુણાકાર લાગુ કરીને ગુણાકાર માળખું નક્કી કરે છે. આ અલગ મૂળની ગુણાકાર ક્યાં છે તે લખવાની મંજૂરી આપે છે. (અગ્રણી ગુણાંક ચલ નથી) સાથે ગુણાંક મેળ ખાતા સમીકરણો પર ચલ રાખવા માટે આ સમીકરણ એક વધુ પડતી નિર્ધારિત પ્રણાલી છે. મોટાભાગના કિસ્સાઓમાં લઘુત્તમ ચોરસ દ્રાવણ હવે ખરાબ સ્થિતિમાં નથી. બીજું પગલું ગૌસ-ન્યુટન અલ્ગોરિધમને લાગુ કરે છે જે અલગ મૂળ માટે વધુ પડતી નિર્ધારિત પ્રણાલીને હલ કરે છે. વિલિયમ કાહન (1972) દ્વારા શોધાયેલ બહુવિધ મૂળના ભૌમિતિક ગુણધર્મને કારણે બહુવિધ મૂળની સંવેદનશીલતાને નિયમિત કરી શકાય છે અને વધુ પડતા નિર્ધારિત સિસ્ટમ મોડેલ ગુણાકારને જાળવી રાખે છે. સ્ક્વેર-ફ્રી ફેક્ટરાઇઝેશન બહુપદીઓ માટે કે જેમના ગુણાંક પૂર્ણાંકો અથવા તર્કસંગત સંખ્યાઓ તરીકે બરાબર આપવામાં આવે છે, તેમને એવા પરિબળોમાં ફેક્ટરાઇઝ કરવાની એક કાર્યક્ષમ પદ્ધતિ છે કે જે ફક્ત સરળ મૂળ ધરાવે છે અને જેમના ગુણાંક પણ બરાબર આપવામાં આવે છે. આ પદ્ધતિ, જેને સ્ક્વેર-ફ્રી ફેક્ટરાઇઝેશન કહેવામાં આવે છે, તે બહુપદીના બહુવિધ મૂળ પર આધારિત છે, જે બહુપદી અને તેના વ્યુત્પન્નના સૌથી મોટા સામાન્ય ભાજકના મૂળ છે. બહુપદી p નું વર્ગ-મુક્ત ગુણાંકકરણ એ એક ગુણાંકકરણ છે જ્યાં દરેક કાં તો 1 હોય છે અથવા બહુવિધ મૂળ વિનાની બહુપદી હોય છે, અને બે અલગ અલગમાં કોઈ સામાન્ય મૂળ નથી. આ ફેક્ટરાઇઝેશનની ગણતરી કરવાની એક કાર્યક્ષમ પદ્ધતિ યુનનું અલ્ગોરિધમ છે. સંદર્ભ બહુપદી મૂળ શોધવાના અલ્ગોરિધમ્સ