About parallel time computation 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?
Here is the link
Thank you very much.
 A: 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.
