Real polynomial root-finding by means of matrix and polynomial iterations

ریشهابی چندجملهای یکنواخت یک موضوع کلاسیک است که هنوز برای محاسبات مدرن مهم است. اغلب به دنبال ریشه های واقعی چند جمله ای با ضرایب واقعی است. اگر چند جمله ای بدون ریشه غیر واقعی، آنها را می توان تقریبی در هزینه کم محاسبه کرد، اما برای چندجملهای درجه بالا، ریشه های غیر واقعی به طور معمول بسیار بیشتر از موارد واقعی است. این چالش به مدت طولانی شناخته شده است و موضوع به شدت مورد مطالعه قرار گرفته است. با این وجود، ما برخی از ایده ها و تکنیک های جدید را پیشنهاد می کنیم و شتاب چشمگیر الگوریتم های شناخته شده را به دست می آوریم. به منظور دستیابی به پیشرفت ما از همبستگی بین محاسبات با ماتریس ها و چند جملهای، محاسبات ماتریس تصادفی و هندسه پیچیده استفاده می کنیم، تکنیک های تکرار نشانه های ماتریس را گسترش می دهیم و از ساختار ماتریس همراهی چند جمله ای ورودی استفاده می کنیم. نتایج آزمایشات گسترده ما با چندجملهای معیاری و ماتریسهای تصادفی بسیار دلگرم کننده است. به ویژه در تست های ما، تعداد تکرارهایی که برای همگام سازی الگوریتم های ما لازم بود، بسیار آرامی رشد کرد (اگر به طور کلی رشد کرد)، به این دلیل که درجه چند جمله ای ورودی و ابعاد ماتریس ورودی را از 64 تا 1024 افزایش دادیم.