Evgenii Martiushev, Candidate of Sciences (Physics and Mathematics), Associate Professor at the SUSU Institute of Natural Sciences and Mathematics and lecturer at the “VirtUM” Centre for Top-level Academic Programmes in the Field of AI, jointly with his colleagues from Finland and the Czech Republic, have developed a method for automatically building solvers for systems of equations composed of Laurent polynomials. Unlike standard equations studied at school, where variables appear only with non-negative powers, Laurent systems also allow for negative powers. Such systems emerge in various engineering applications, including the development and optimization of computer vision algorithms, navigation of unmanned vehicles, robotics, and acoustics.
To efficiently solve Laurent systems, researchers construct an “elimination template”—a special coefficient matrix that enables solutions to be found using linear algebra methods. Early template generators relied on classical tools of algebraic geometry, such as Gröbner bases and resultants. However, practice has shown that empirical approaches are often more effective. The method proposed by the researchers is based on an iterative empirical scheme. Its main advantage is versatility: it can generate solvers even for systems with positive-dimensional solution components and can automatically detect and take into account certain symmetries of Laurent systems. At the same time, the method does not require deep mathematical expertise from the user—only functions for the computing system coefficients need to be specified. The generator then produces several template options, allowing the user to select the fastest and most accurate one.
“We tested our generator on various problems, mainly in geometric computer vision,” Evgenii Martiushev and his colleagues note in their article. “These include optimal three-view triangulation, hybrid navigation, and time-of-arrival self-calibration. Experiments show that our solvers are both more accurate and faster than the existing alternatives.”
Let us clarify what applied tasks we are talking about.
One application is optimal three-view triangulation. Suppose that three cameras capture the same object (for example, an architectural monument or a film set) from different angles. To create an accurate 3D model, the computer must find a point in space, the projection of which optimally aligns with all three images. The proposed solver enables faster and more accurate reconstruction, which is important for applications ranging from film visual effects to digital twins of cities.
Another application is hybrid navigation (semi-generalized hybrid pose estimation). In this case, we have a standard camera on a smartphone and a complex "generalized" camera (for example, a multi-lens system on a self-driving car). The task is to combine their data to understand the car's location relative to the smartphone.
The new solver, proposed by Evgenii Martiushev, performs this task 20–30 times faster than the existing algorithms, which is crucial for real-time smart city traffic monitoring systems.
A third application is time-of-arrival self-calibration. For instance, there are several speakers and microphones located in a room. Knowing only the time it takes for the sound to travel from the speaker to the microphone (time-of-arrival), the system must automatically calculate the locations of all the devices.
This is essential for creating smart conference rooms and noise-cancellation systems. Here, the new method for configurations with four speakers and six microphones (as well as five speakers and five microphones) proved to be 1.5-1.8 times faster than the leading global solutions.
The method has also previously been successfully applied in robotics to develop an efficient solver for the forward kinematics of parallel manipulators.
The research has been published in the International Journal of Computer Vision, ranked in the TOP 1% of Scopus and Web of Science journals.
The research was carried out as part of the implementation of a top-level programme in the field of artificial intelligence with the support from the "Analytical Centre for the Government of the Russian Federation" Autonomous Non-Commercial Organization.