17:00
On the shatter functions of semilinear families
Abstract
Toward a characterization of modularity using shatter functions, we show that an o-minimal expansion of the real ordered additive group $(\mathbb{R}; 0, +,<)$ does not define restricted multiplication if and only if the shatter function of every definable family is asymptotic to a polynomial. Our result implies that vc-density can only take integer values in $(\mathbb{R}; 0, +,<)$ confirming a special case of a conjecture by Chernikov. (Joint with Abdul Basit.)
Balancing Inexactness in Matrix Computations
Abstract
On supercomputers that exist today, achieving even close to the peak performance is incredibly difficult if not impossible for many applications. Techniques designed to improve the performance of matrix computations - making computations less expensive by reorganizing an algorithm, making intentional approximations, and using lower precision - all introduce what we can generally call ``inexactness''. The questions to ask are then:
1. With all these various sources of inexactness involved, does a given algorithm still get close enough to the right answer?
2. Given a user constraint on required accuracy, how can we best exploit and balance different types of inexactness to improve performance?
Studying the combination of different sources of inexactness can thus reveal not only limitations, but also new opportunities for developing algorithms for matrix computations that are both fast and provably accurate. We present few recent results toward this goal, icluding mixed precision randomized decompositions and mixed precision sparse approximate inverse preconditioners.