POLAR is a high performance open-source software package to compute the polar decomposition ((PD)) of a dense matrix A = UH based on QR-based Dynamically Weighted Halley (QDWH) and ZOLO-PD algorithms.
The QR-based Dynamically Weighted Halley (QDWH) is one of the most popular algorithms to compute the polar decomposition. It is backward stable and converges in at most six iterations.
ZOLO-PD relies on the Zolotarev function which is the best rational approximant to the sign function
for computing the polar decomposition.
Building upon on the QR-based
Dynamically Weighted Halley (QDWH) algorithm, the key idea
lies in finding the best rational approximation for the scalar sign function,
which also corresponds to the polar factor for symmetric matrices,
to further accelerate the QDWH convergence.
Based on the Zolotarev rational functions---introduced by Zolotarev (ZOLO) in
1877--- this new PD algorithm ZOLO-PD converges within two iterations even for ill-conditioned matrices,
instead of the original six iterations needed for QDWH.
ZOLO-PD uses the property of Zolotarev functions that optimality is maintained when
two functions are composed in an appropriate manner.
The resulting ZOLO-PD has a convergence rate up to seventeen,
in contrast to the cubic convergence rate for QDWH.
This comes at the price of higher arithmetic costs and memory footprint. These
extra floating-point operations can, however, be processed in an
embarrassingly parallel fashion.
Programming models and backends:
The installation requires at least CMake of version 3.2.3. To build the polar decomposition based on QDWH/ZOLOPD, follow these instructions:
Get polar from git repository
git clone git@github.com:ecrc/polarGo into polar folder
cd polarCreate build directory and go there
mkdir build && cd buildUse CMake to get all the dependencies
cmake .. -DCMAKE_INSTALL_PREFIX=/path/to/install/ To use exist dependencies
cmake .. -DCMAKE_INSTALL_PREFIX=/path/to/install/ -DSCALAPACK_DIR=/path/to/scalapack/install/ -DSLTMG_LIBRARIES=/path/to/scalapack/install/lib/libsltmg.aTo build the testing binaries (optional) add the following:
-DPOLAR_TESTING:BOOL=ONBuild polar
make -jInstall polar
make installAdd line
export PKG_CONFIG_PATH=/path/to/install/lib/pkgconfig:$PKG_CONFIG_PATHto your .bashrc file.
Now you can use pkg-config executable to collect compiler and linker flags for polar based on QDWH/ZOLO-PD.
The directories testing and timing contain an example to test the accuracy and the performance of QDWH/ZOLO-PD using ill (with condition number less than 5.e12) and well-conditioned random matrices.
The complete list of options is available below with -h option:
"======= QDWH/ZOLOPD testing using ScaLAPACK\n"
" -p --nprow : Number of MPI process rows\n"
" -q --npcol : Number of MPI process cols\n"
" -jl --lvec : Compute left singular vectors\n"
" -jr --rvec : Compute right singular vectors\n"
" -n --N : Dimension of the matrix\n"
" -b --nb : Block size\n"
" -m --mode : [1:6] Mode from pdlatms used to generate the matrix\n"
" -k --cond : Condition number used to generate the matrix\n"
" -o --optcond : Estimate Condition number using QR\n"
" -i --niter : Number of iterations\n"
" -r --n_range : Range for matrix sizes Start:Stop:Step\n"
" -c --check : Check the solution\n"
" -v --verbose : Verbose\n"
" -h --help : Print this help\n" ); On Cray systems, the launching command typically looks like:
srun --ntasks=nT --hint=nomultithread ./main --nprow p --npcol q --b 64 --cond 1e16 --niter 1 --n_range start:stop:step --check
1. The number of the nodes is N, the number of tasks (nT) = N * (number_of_cores per node ). The programming model is pure MPI (no OpenMP, i.e., sequential BLAS).
2. PxQ is the process grid configuration, where (nT - PxQ = 0)Please feel free to create an issue on Github for any questions and inquiries.