Poster 2019

CASC2019

   

Proceedings

   
   Invited Talks

 

Poslavsky Stanislav Vladimirovich

Institut of High Energy Physics, Protvino, Russia

 

Rings: an efficient JVM library for commutative algebra

 

Rings is an efficient lightweight library for commutative algebra written in Java and Scala languages. Polynomial arithmetic, GCDs, polynomial factorization and Groebner bases are implemented with the use of modern asymptotically fast algorithms. Rings can be easily interacted or embedded in applications via a simple API with fully typed hierarchy of algebraic structures and algorithms for commutative algebra. The use of the Scala language brings a quite novel powerful, strongly typed functional programming model allowing to write short, expressive, and fast code for applications. At the same time Rings shows one of the best performances among existing software for algebraic calculations. Specific attention in the talk will be paid to the design patterns, implementational aspects, benchmarks and some practical applications. 


Chee Yap

Courant Institute of Mathematical Science, New York

 

Towards Soft Exact Computation:

 

Exact geometric computation (EGC) is the most successful general approach for achieving robust numerical algorithms that satisfy geometric constraints. At the heart of EGC are various zero problems. (A) Many zero problems are not-known to be decidable. (B) When decidable, they may have high complexity (e.g., algebraic zero problems). (C) Even when the complexity is non-limiting, there may be no simple pathway to correct and practical implementation. In many applications, it is possible to side-step the zero problem by formulating suitable ``soft zero problems''. E.g., we replace zeros by ``natural clusters'' of zeros or exact predicates by ``soft predicates''. This talk will illustrate the power of soft approaches in root isolation, robot motion planning and generalized Voronoi diagrams. Our algorithms (a) have adaptive complexity, (b) are practical and (c) relatively easy to implement correctly.