Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleTriangular -basis decompositions and derandomization of linear algebra algorithms over
Author(s) Somit Gupta, Soumojit Sarkar, Arne Storjohann, Johnny Valeriote
TypeArticle in Journal
AbstractDeterministic algorithms are given for some computational problems that take as input a nonsingular polynomial matrix A over K [ x ] , K an abstract field, including solving a linear system involving A and computing a row reduced form of A . The fastest known algorithms for linear system solving based on the technique of high-order lifting by Storjohann (2003), and for row reduction based on the fast minimal approximant basis computation algorithm by Giorgi et al. (2003), use randomization to find either a linear or small degree polynomial that is relatively prime to det A . We derandomize these algorithms by first computing a factorization of A = U H , with x not dividing det U and x − 1 not dividing det H . A partial linearization technique, that is applicable also to other problems, is developed to transform a system involving H , which may have some columns of large degrees, to an equivalent system that has degrees reduced to that of the average column degree.
KeywordsPolynomial matrices, Linear system solving, Row reduction, Derandomization
URL http://www.sciencedirect.com/science/article/pii/S0747717111001416
JournalJournal of Symbolic Computation
Pages422 - 453
NoteSpecial Issue for Joachim von zur Gathen at 60
Translation No
Refereed No