Efficient linear algebra for embedded optimization and its use in the HPMPC solver

Dense linear algebra routines play a key role in the efficient implementation of solvers for embedded optimization, since they account for most of the computational burden. This is especially true for second order optimization methods, that make use of matrix-matrix operations and factorizations. Tailored triple-loop based linear algebra (even if code generated) can generally attain only a small fraction of the computational throughput in modern CPUs. Conversely, standard linear algebra libraries (such as BLAS) are optimized for large-scale performance, and often perform poorly on small matrices typical of embedded optimization. This talk presents some dense linear algebra implementation techniques specially tailored to embedded optimization. The routines implemented using these techniques can attain a large fraction of the computational throughput also for small matrices, and have the potential to find application in a wide range of solvers for embedded optimization. In particular, the use of these routines in the HPMPC solver (that is a Riccati-based interior point method for the linear MPC problem) is used as a showcase for the proposed implementation techniques.