Open problems in computational linear algebra Original Research Article

In the recent past a few important open problems such as those involving developing polynomial-time iterative algorithms for solving linear programs in both integer and real number models and for testing and generating primes have been solved. There are still several problems we have not found solutions over decades/centuries. Problems such as those involving (i) devising a deterministic noniterative polynomial-time algorithm for linear programs, (ii) deciding a priori all required fail-proof prime bases for errorfree computations for linear systems and linear optimization, (iii) determining computational complexities in some deterministic algorithms, (iv) designing algorithms with the lowest possible bound of complexity for matrix multiplications, (v) developing a polynomial-time deterministic algorithm for computing the error-bounds in an error-free computation, (vi) verification of the solution of some nonlinear optimization problems in polynomial time, (vii) obtaining the error-bounds in the solution of some linear/nonlinear problems when solved probabilistically are open problems. The solution of these open problems has the potential to revolutionize the whole area of computational mathematics and science as well as super-/grid-computing. We present here some of these open problems precisely along with the related discussions.