tree d0dec22184e7b690ab70a51722cc0953dfd90bb7
parent 2ffddaccfe5905957ce2ecad26e3b360107fd49c
author Sameer Agarwal <sameeragarwal@google.com> 1563582764 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1565014541 -0700

Add a specialized schur eliminator.

Add a new specialized Schur Eliminator for the case where there is
exactly one F block and all dimensions are known at compile time.

Benchmark on my macbook shoes ~3x speedup for Eliminate and 4x speedup for BackSubstitute.
Similar speedups are observed on other platforms.

------------------------------------------------------------------------------------------
Benchmark                                                   Time           CPU Iterations
------------------------------------------------------------------------------------------
BM_SchurEliminatorEliminate/10                           4176 ns       4132 ns     153522
BM_SchurEliminatorEliminate/64                          24392 ns      24234 ns      29993
BM_SchurEliminatorEliminate/512                        169632 ns     168709 ns       3872
BM_SchurEliminatorEliminate/4096                      1296407 ns    1292873 ns        519
BM_SchurEliminatorEliminate/10000                     3159652 ns    3149532 ns        216
BM_SchurEliminatorForOneFBlockEliminate/10               1187 ns       1184 ns     603953
BM_SchurEliminatorForOneFBlockEliminate/64               7917 ns       7898 ns      87558
BM_SchurEliminatorForOneFBlockEliminate/512             57629 ns      57485 ns      12035
BM_SchurEliminatorForOneFBlockEliminate/4096           484680 ns     480757 ns       1459
BM_SchurEliminatorForOneFBlockEliminate/10000         1157237 ns    1150735 ns        566
BM_SchurEliminatorBackSubstitute/10                       681 ns        679 ns    1070500
BM_SchurEliminatorBackSubstitute/64                      3899 ns       3887 ns     182883
BM_SchurEliminatorBackSubstitute/512                    33632 ns      33467 ns      22582
BM_SchurEliminatorBackSubstitute/4096                  241117 ns     240257 ns       2884
BM_SchurEliminatorBackSubstitute/10000                 631869 ns     626992 ns       1146
BM_SchurEliminatorForOneFBlockBackSubstitute/10           139 ns        138 ns    5021341
BM_SchurEliminatorForOneFBlockBackSubstitute/64           898 ns        892 ns     780396
BM_SchurEliminatorForOneFBlockBackSubstitute/512         7344 ns       7286 ns      87059
BM_SchurEliminatorForOneFBlockBackSubstitute/4096       57634 ns      57345 ns      11642
BM_SchurEliminatorForOneFBlockBackSubstitute/10000     153129 ns     152320 ns       4949

Change-Id: Iae64e96c91beb44b807df0e0572d202df7cdaed8