hrvatski

Složenost metoda silaska za polinomne jednadžbe

Analizira se sekvencijalna i paralelna složenost nekih metoda silaska. Pokazuje se da originalne formulacije tih metoda imaju eksponencijalnu složenost u ovisnosti o stupnju polinoma p. Kellenbergerova metoda silaska modificirana je tako da ima, u najgorem slučaju, polinomnu složenost. To dokazuje da su metode silaska usporedive po efikasnosti s najpoznatijim globalno konvergentnim metodama za nalaženje nultočaka polinoma. Ovo proširuje novije rezultate Shuba, Smalea, Pana, Binija i ostalih na klasu metoda silaska. Rezultati numeričkog testiranja potvržuju efikasnost i točnost predloženih algoritama.

Kompleksnost; polinomi; metode silaska

nije evidentirano