Paper Info
Title
Block solution of sparse linear systems over GF (q): the singular case
Abstract
Probabilistic algorithms based on the Krylov / Wiedemann or the Lanczos method to solve non homogeneous N x N systems Ax = b over a Galois field GF(q), usually require 2N matrix---vector products and O(n2+o(1)) additional arithmetic operations. Only the block Wiedemann algorithm, as given by Kaltofen in [6], has the least number (1+ε)N+O(1) of matrix---vector products of any known algorithm. We extend its analysis to the case of singular matrices A.
Year
DOI
Venue
1998
10.1145/307733.307737
ACM SIGSAM Bulletin
Keywords
Field
DocType
sparse linear system,galois field,vector product,additional arithmetic operation,lanczos method,non homogeneous n,singular case,known algorithm,probabilistic algorithm,n system,block wiedemann algorithm,block solution,singular matrix
Discrete mathematics,Combinatorics,Lanczos resampling,Linear system,Homogeneous,Matrix (mathematics),Probabilistic analysis of algorithms,Block Wiedemann algorithm,Galois theory,Mathematics
Journal
Volume
Issue
Citations 
32
4
1
PageRank 
References 
Authors
0.38
6
1
Name
Order
Citations
PageRank
Gilles Villard156548.04