I am studying a paper where it is mentioned that Newton iteration may be used to compute the inverse of $n \times n$, well- conditioned matrix in parallel time $o(\log^2n)$ and that this computation is processor efficient. I want to understand meaning of this term. What is parallel time computation and how can this be useful for any iteration method?
Thank you very much.
What is meant here is more in the realm of computer science than pure mathematics, so if you don't have a strong computer background it may help to read the Wiki entry on Parallel Computing. Basically, a parallel algorithm is used to let multiple processor cores act at the same time rather than a single core acting alone. The efficiency of a parallel algorithm is based on a measurement of parallel time, which is defined as the time it takes for the parallel algorithm to run. To be considered efficient, the algorithm must satisfy: $$T_{sequential} \approx T_{parallel} * N_{cores}$$ Where $T_{sequential}$ is the run time of best known serial algorithm.
The efficiency of the parallel algorithm you referenced is then given in terms of poly-logarithmic time: $O (\log^c(n))$ where c is a constant and n is the size of the data set. See the Wiki article on time complexity for a more detailed explanation of poly-logarithmic (and other) time scales.
It is also interesting to note that iterative algorithms such as Newton's method are usually considered inherently serial, i.e. quite difficult to (efficiently) parallelize.