zbMATH — the first resource for mathematics

Random matrices over a DVR and LU factorization. (English) Zbl 1316.65038
Summary: Let \(R\) be a discrete valuation ring (DVR) and \(K\) be its fraction field. If \(M\) is a matrix over \(R\) admitting an LU decomposition, it could happen that the entries of the factors \(L\) and \(U\) do not lie in \(R\), but just in \(K\). Having a good control on the valuations of these entries is very important for algorithmic applications. In the paper, we prove that on average these valuations are not too large and explain how one can apply this result to provide an efficient algorithm computing a basis of a coherent sheaf over \(\mathbb{A}_K^1\) from the knowledge of its stalks.

65F05 Direct numerical methods for linear systems and matrix inversion
16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras)
Full Text: DOI
[1] Abdel-Ghaffar, K., The determinant of random power series matrices over finite fields, Linear Algebra Appl., 315, 139-144, (2000) · Zbl 0964.15016
[2] Caruso, X.; Lubicz, D., Semi-simplifiée modulo p des représentations semi-stables: une approche algorithmique, prepublication, available at
[3] Evans, S., Elementary divisors and determinants of random matrices over a local field, Stoch. Process. Appl., 102, 89-102, (2002) · Zbl 1075.15500
[4] Hafner, J. L.; McCurley, K. S., Asymptotically fast triangularization of matrices over rings, SIAM J. Comput., 20, 1068-1083, (1991) · Zbl 0738.68050
[5] Householder, A., The theory of matrices in numerical analysis, (1975), Dover New York
[6] Vassilevska Williams, V., Multiplying matrices faster than coppersmith-Winograd, (STOC’12, (2012)) · Zbl 1286.65056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.