Abstract: This paper first describes the steps involved in primal-dual interior point algorithm and explains which step in it can be parallelized. Next the theory of the QR decomposition is also detailed. It also points out how to use the QR decomposition to solve the linear simultaneous equations parallelly. In conclusion, it proposes a parallel primal-dual interior point algorithm based on the QR decomposition and lists some test results.

Key words: parallelism, primal-dual interior point algorithm