@inproceedings{10.1145/860854.860889,
    Abstract = {We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean ntimes n matrices in K[x] of degree bounded by d, with K a commutative field. Under the straight-line program model we show that multiplication is reducible to the problem of computing the coefficient of degree d of the determinant. Conversely, we propose algorithms for minimal approximant computation and column reduction that are based on polynomial matrix multiplication; for the determinant, the straight-line program we give also relies on matrix product over K[x] and provides an alternative to the determinant algorithm of [16, 17]. We further show that all these problems can be solved in particular in O ({$\omega$}) operations in K. Here the "soft O" notation O indicates some missing log (nd) factors and {$\omega$} is the exponent of matrix multiplication over K.},
    Address = {New York, NY, USA},
    Author = {Giorgi, Pascal and Jeannerod, Claude-Pierre and Villard, Gilles},
    BookTitle = {Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation},
    File = {On the Complexity of Polynomial Matrix Computations - issac03 - a - w.pdf},
    ISBN = {1581136412},
    Keywords = {minimal basis, polynomial matrix multiplication, matrix gcd, matrix polynomial, column reduced form, determinant},
    Location = {Philadelphia, PA, USA},
    Pages = {135--142},
    Publisher = {Association for Computing Machinery},
    Series = {ISSAC '03},
    Title = {On the Complexity of Polynomial Matrix Computations},
    URL = {https://doi.org/10.1145/860854.860889},
    Year = {2003},
    bdsk-url-1 = {https://doi.org/10.1145/860854.860889},
    date-added = {2020-09-29 08:14:00 +0200},
    date-modified = {2020-09-29 08:14:00 +0200},
    numpages = {8},
    doi = {10.1145/860854.860889}
}

@inproceedings{10.1145/860854.860889, Abstract = {We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean ntimes n matrices in K[x] of degree bounded by d, with K a commutative field. Under the straight-line program model we show that multiplication is reducible to the problem of computing the coefficient of degree d of the determinant. Conversely, we propose algorithms for minimal approximant computation and column reduction that are based on polynomial matrix multiplication; for the determinant, the straight-line program we give also relies on matrix product over K[x] and provides an alternative to the determinant algorithm of [16, 17]. We further show that all these problems can be solved in particular in O ({$\omega$}) operations in K. Here the "soft O" notation O indicates some missing log (nd) factors and {$\omega$} is the exponent of matrix multiplication over K.}, Address = {New York, NY, USA}, Author = {Giorgi, Pascal and Jeannerod, Claude-Pierre and Villard, Gilles}, BookTitle = {Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation}, File = {On the Complexity of Polynomial Matrix Computations - issac03 - a - w.pdf}, ISBN = {1581136412}, Keywords = {minimal basis, polynomial matrix multiplication, matrix gcd, matrix polynomial, column reduced form, determinant}, Location = {Philadelphia, PA, USA}, Pages = {135--142}, Publisher = {Association for Computing Machinery}, Series = {ISSAC '03}, Title = {On the Complexity of Polynomial Matrix Computations}, URL = {https://doi.org/10.1145/860854.860889}, Year = {2003}, bdsk-url-1 = {https://doi.org/10.1145/860854.860889}, date-added = {2020-09-29 08:14:00 +0200}, date-modified = {2020-09-29 08:14:00 +0200}, numpages = {8}, doi = {10.1145/860854.860889} }