Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix

DOI10.1145/3476446.3535495MaRDI QIDQ6391525zbMATH OpenWikidataFDO

Authors G. Labahn, Vincent Neiger, Thi Xuan Vu, Wei Zhou

Publication date 18 February 2022

Full work available at URL https://doi.org/10.1145/3476446.3535495

Abstract: Consider a matrix

m a t h b f F i n m a t h b b K [x]^{m i m e s n}

of univariate polynomials over a field

m a t h b b K

. We study the problem of computing the column rank profile of

m a t h b f F

. To this end we first give an algorithm which improves the minimal kernel basis algorithm of Zhou, Labahn, and Storjohann (Proceedings ISSAC 2012). We then provide a second algorithm which computes the column rank profile of

m a t h b f F

with a rank-sensitive complexity of

O i l d e (r^{o m e g a - 2} n (m + D))

operations in

m a t h b b K

. Here,

D

is the sum of row degrees of

m a t h b f F

,

o m e g a

is the exponent of matrix multiplication, and

O i l d e (c d o t)

hides logarithmic factors.

This page was built for publication: Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391525)