A new parallel normalized optimized approximate inverse algorithm for computing explicitly approximate inverses, is introduced for symmetric multiprocessor (SMP) systems. The parallelization of the approximate inverse has been implemented by an antidiagonal motion, in order to overcome the data dependencies. The parallel normalized explicit approximate inverses are used in conjuction with parallel normalized explicit preconditioned conjugate gradient schemes, for the efficient solution of finite element sparse linear systems. The parallel design and implementation issues of the new algorithms are discussed and the parallel performance is presented, using OpenMP. The speedups tend to the upper theoretical bounds for all cases making approximate inverse preconditioning suitable for SMP systems.