  Gaussian elimination with no pivoting and block Gaussian elimination are
attractive alternatives to the customary but communication intensive Gaussian
elimination with partial pivoting (hereafter we use the acronyms GENP, BGE, and
GEPP} provided that the computations proceed safely and numerically safely},
that is, run into neither division by 0 nor numerical problems. Empirically,
safety and numerical safety of GENP have been consistently observed in a number
of papers where an input matrix was pre-processed with various structured
multipliers chosen ad hoc. Our present paper provides missing formal support
for this empirical observation and explains why it was elusive so far. Namely
we prove that GENP is numerically unsafe for a specific class of input matrices
in spite of its pre-processing with some well-known and well-tested structured
multipliers, but we also prove that GENP and BGE are safe and numerically safe
for the average input matrix pre-processed with any nonsingular and
well-conditioned multiplier. This should embolden search for sparse and
structured multipliers, and we list and test some new classes of them. We also
seek randomized pre-processing that universally (that is, for all input
matrices) supports (i) safe GENP and BGE with probability 1 and/or (ii)
numerically safe GENP and BGE with a probability close to 1.We achieve goal (i)
with a Gaussian structured multiplier and goal (ii) with a Gaussian
unstructured multiplier and alternatively with Gaussian structured
augmentation. We consistently confirm all these formal results with our tests
of GENP for benchmark inputs. We have extended our approach to other
fundamental matrix computations and keep working on further extensions.
