On the Algorithmic Linearizability of Nonlinear Ordinary Differential Equations

D. A. Lyakhov, V. P. Gerdt, and D. L. Michels.

Journal of Symbolic Computation, Elsevier (2019).

Solving nonlinear ordinary differential equations is one of the fundamental and practically important research challenges in mathematics. However, the problem of their algorithmic linearizability so far remained unsolved. In this contribution, we propose a solution of this problem for a wide class of nonlinear ordinary differential equation of arbitrary order. We develop two algorithms to check if a nonlinear differential equation can be reduced to a linear one by a point transformation of the dependent and independent variables. In this regard, we have restricted ourselves to quasi-linear equations with a rational dependence on the occurring variables and to point transformations. While the first algorithm is based on a construction of the Lie point symmetry algebra and on the computation of its derived algebra, the second algorithm exploits the differential Thomas decomposition and allows not only to test the linearizability, but also to generate a system of nonlinear partial differential equations that determines the point transformation and the coefficients of the linearized equation. The implementation of our algorithms is discussed and evaluated using several examples.

(to appear)

A Strongly Consistent Finite Difference Scheme for Steady Stokes Flow and its Modified Equations

Y. A. Blinkov, V. P. Gerdt, D. A. Lyakhov, and D. L. Michels.

Computer Algebra in Scientific Computing (CASC 2018), Springer (2018).

We construct and analyze a strongly consistent second-order finite difference scheme for the steady two-dimensional Stokes flow. The pressure Poisson equation is explicitly incorporated into the scheme. Our approach suggested by the first two authors is based on a combination of the finite volume method, difference elimination, and numerical integration. We make use of the techniques of the differential and difference Janet/Gröbner bases. In order to prove strong consistency of the generated scheme we correlate the differential ideal generated by the polynomials in the Stokes equations with the difference ideal generated by the polynomials in the constructed difference scheme. Additionally, we compute the modified differential system of the obtained scheme and analyze the scheme's accuracy and strong consistency by considering this system. An evaluation of our scheme against the established marker-and-cell method is carried out.

arXiv

Teaching UAVs to Race: End-to-End Regression of Agile Controls in Simulation

M. Mueller, V. Casser, N. Smith, D. L. Michels, and B. Ghanem.

Second International Workshop on Computer Vision for UAVs (UAVision 2018), European Conference on Computer Vision (ECCV 2018).

Automating the navigation of unmanned aerial vehicles (UAVs) in diverse scenarios has gained much attention in recent years. However, teaching UAVs to fly in challenging environments remains an unsolved problem, mainly due to the lack of training data. In this paper, we train a deep neural network to predict UAV controls from raw image data for the task of autonomous UAV racing in a photo-realistic simulation. Training is done through imitation learning with data augmentation to allow for the correction of navigation mistakes. Extensive experiments demonstrate that our trained network (when sufficient data augmentation is used) outperforms state-of-the-art methods and flies more consistently than many human pilots. Additionally, we show that our optimized network architecture can run in real-time on embedded hardware, allowing for efficient on- board processing critical for real-world deployment.

Best Paper/Presentation Award.

Paper (PDF) KAUST News

A Quantitative Platform for Non-Line-of-Sight Imaging Problems

J. Klein, M. Laurenzis, D. L. Michels, and M. B. Hullin.

British Machine Vision Conference (BMVC 2018), British Machine Vision Association (2018).

The computational sensing community has recently seen a surge of works on imaging beyond the direct line of sight. However, most of the reported results rely on drastically different measurement setups and algorithms, and are therefore hard to impossible to compare quantitatively. Here, we focus on an important class of approaches, namely those that that aim to reconstruct scene properties from time-resolved optical impulse responses. In this paper, we introduce a collection of reference data and quality metrics that are tailored to the most common use cases, and we define reconstruction challenges that we hope will aid the development and assessment of future methods.

Project Page Paper (PDF) Supplementary Material (PDF)

Conjugated Polymers as a New Class of Dual-Mode Matrices for MALDI Mass Spectrometry and Imaging

K. Horatz, M. Giampà, Y. Karpov, K. Sahre, H. Bednarz, A. Kiriy, B. Voit, K. Niehaus, N. Hadjichristidis, D. L. Michels, and F. Lissel.

Journal of the American Chemical Society, American Chemical Society (2018).

Matrix-Assisted Laser Desorption/Ionization Mass Spectrometry MALDI MS and MALDI MS Imaging are ubiquitous analytical methods in medical, pharmaceutical, biological and environmental research. Currently, there is a strong interest in the investigation of low molecular weight compounds (LMWCs), especially to trace and understand metabolic pathways, requiring the development of new matrix systems which have favorable optical properties, a high ionization efficiency, and are MALDI silent in the LMWC area. In this paper, five conjugated polymers, poly[naphthalene-diimide-bithiophene] (PNDI(T2)), poly[3-dodecylthiophene] (P3DDT), poly[2,3-bis-(3-octyloxyphenyl)quinoxaline-5,8-diyl-alt-thiophene-2,5-diyl] (PTQ1), poly[isoindigo-bithiophene] (PII(T2)), and poly[9,9-octylfluorene] (P9OFl) are investigated as matrices. The polymers have a strong optical absorption, are solution-processable, and can be coated into thin films, allowing to vastly reduce the amount of matrix used. All investigated polymers function as matrices in both positive and negative mode MALDI, classifying them as rare dual-mode matrices, and show a very good analyte ionization ability in both modes. PNDI(T2), P3DDT, PTQ1, and PII(T2) are MALDI silent in the full measurement range (> m/z = 150k), except at high laser intensities. In MALDI MS experiments of single analytes and a complex biological sample, the performance of the polymers was found to be as good as two commonly used matrices (2,5-DHB for positive, and 9AA for negative mode measurements). The detection limit of two standard analytes was determined being below 164 pmol for reserpine (RP) and below 245 pmol for cholic acid (ChA). Additionally P3DDT was used successfully in first MALDI MS Imaging experiments allowing to visualize the tissue morphology of rat brain sections.

Selected for ACS Editors' Choice, JACS Spotlight, and supplementary journal cover (open access).

Featured by KAUST's Discovery, Phys.org, AAAS's EurekAlert!, and the COMPAMED Magazine.

JACS Discovery Phys.org EurekAlert! COMPAMED

Concentrated Mixed Cation Acetate "Water-in-Salt" Solutions as Green and Low Cost High Voltage Electrolytes for Aqueous Batteries

M. R. Lukatskaya, J. Feldblyum, D. G. Mackanic, F. Lissel, D. L. Michels, Y. Cui, and Z. Bao.

Energy & Environmental Science, Royal Society of Chemistry (2018).

Electrolyte solutions are a key component of energy storage devices that significantly impact capacity, safety, and cost. Recent developments in "water-in-salt" (WIS) aqueous electrolyte research have enabled the demonstration of aqueous Li-ion batteries that operate with capacities and cyclabilities comparable with those of commercial non-aqueous Li-ion batteries. Critically, the use of aqueous electrolyte mitigates safety risks associated with non-aqueous electrolytes. However, the high cost and potential toxicity of imide-based WIS electrolytes limit their practical deployment. In this report, we disclose the efficacy of inexpensive, non-toxic mixed cation electrolyte systems for Li-ion batteries that otherwise provide the same benefits as current WIS electrolytes: extended electrochemical stability window and compatibility with traditional intercalation Li-ion battery electrode materials. We take advantage of the high solubility of potassium acetate to achieve the WIS condition in a eutectic mixture of lithium and potassium acetate; with water-to-cation ratio as low as 1.3. Our work suggests an important direction for the practical realization of safe, low-cost, and high-performance Li-ion batteries.

Selected as an outstanding "hot article" by the editors (open access).

Royal Society of Chemistry

Explicit Exponential Rosenbrock Methods and their Application in Visual Computing

V. T. Luan and D. L. Michels.

arXiv:1805.08337, Cornell University Library (2018).

We introduce a class of explicit exponential Rosenbrock methods for the time integration of large systems of stiff differential equations. Their application with respect to simulation tasks in the field of visual computing is discussed where these time integrators have shown to be very competitive compared to standard techniques. In particular, we address the simulation of elastic and nonelastic deformations as well as collision scenarios focusing on relevant aspects like stability and energy conservation, large stiffnesses, high fidelity and visual accuracy.

arXiv

OIL: Observational Imitation Learning

G. Li, M. Mueller, V. Casser, N. Smith, D. L. Michels, and B. Ghanem.

arXiv:1803.01129, Cornell University Library (2018).

Recent work has explored the problem of autonomous navigation by imitating a teacher and learning an end-to-end policy, which directly predicts controls from raw images. However, these approaches tend to be sensitive to mistakes by the teacher and do not scale well to other environments or vehicles. To this end, we propose Observational Imitation Learning (OIL), a novel imitation learning variant that supports online training and automatic selection of optimal behavior by observing multiple imperfect teachers. We apply our proposed methodology to the challenging problems of autonomous driving and UAV racing. For both tasks, we utilize the Sim4CV simulator that enables the generation of large amounts of synthetic training data and also allows for online learning and evaluation. We train a perception network to predict waypoints from raw image data and use OIL to train another network to predict controls from these waypoints. Extensive experiments demonstrate that our trained network outperforms its teachers, conventional imitation learning (IL) and reinforcement learning (RL) baselines and even humans in simulation.

arXiv Project Page

Geometric-Integration Tools for the Simulation of Musical Sounds

A. Ishikawa, D. L. Michels, and T. Yaguchi.

Japan Journal of Industrial and Applied Mathematics, Springer (2018).

During the last decade, much attention has been given to sound rendering and the simulation of acoustic phenomena by solving appropriate models described by Hamiltonian partial differential equations. In this contribution, we introduce a procedure to develop appropriate tools inspired from geometric integration in order to simulate musical sounds. Geometric integrators are numerical integrators of excellent quality that are designed exclusively for Hamiltonian ordinary differential equations. The introduced procedure is a combination of two techniques in geometric integration: the semi-discretization method by Celledoni et al. (J Comput Phys 231:6770–6789, 2012) and symplectic partitioned Runge–Kutta methods. This combination turns out to be a right procedure that derives numerical schemes that are effective and suitable for computation of musical sounds. By using this procedure we derive a series of explicit integration algorithms for a simple model describing piano sounds as a representative example for virtual instruments. We demonstrate the advantage of the numerical methods by evaluating a variety of numerical test cases.

Springer Link Paper (PDF) BibTeX

Über Konzeption und Methodik computergestützter Simulationen

D. L. Michels.

Human and Technology in the Digital Age, Springer (2018).

Die computergestützte Simulation hat sich im Zuge steigender konzeptioneller und technischer Möglichkeiten zu einer zentralen Kulturtechnik herausgebildet. Neben klassischer Theorie und Experiment stellt sie nunmehr einen gleichberechtigten digitalen Methodenapparat zu Analyse und Vorhersage und schließlich zur Schaffung wissenschaftlicher Erkenntnisse dar. Die Auslagerung schwieriger Problemstellungen in die digitale Welt ermöglicht in vielen Fällen deren effiziente Lösung und läßt in ihrer inversen Formulierung die Bewältigung komplexer Optimierungsprobleme zu. Umgekehrt erlaubt sie die Steuerung digitaler Systeme sowie deren Reaktion im Hinblick auf sensorische Dateneingaben und läßt dadurch eine adäquate Interaktion dieser Systeme mit ihrer realen Umwelt zu. Dieser Beitrag führt unter konzeptionellen Gesichtspunkten in die Grundlagen computergestützter Simulationen ein und diskutiert Möglichkeiten und Grenzen des resultierenden technischen Methodenapparats.

(to appear)

Multi-Scale Terrain Texturing using Generative Adversarial Networks

J. Klein, S. Hartmann, M. Weinmann, and D. L. Michels.

Image and Vision Computing New Zealand (IVCNZ 2017), IEEE Xplore Digital Library (2017).

We propose a novel, automatic generation process for detail maps that allows the reduction of tiling artifacts in real-time terrain rendering. This is achieved by training a generative adversarial network (GAN) with a single input texture and subsequently using it to synthesize a huge texture spanning the whole terrain. The low-frequency components of the GAN output are extracted, down-scaled and combined with the high-frequency components of the input texture during rendering. This results in a terrain texture that is both highly detailed and non-repetitive, which eliminates the tiling artifacts without decreasing overall image quality. The rendering is efficient regarding both memory consumption and computational costs. Furthermore, it is orthogonal to other techniques for terrain texture improvements such as texture splatting and can directly be combined with them.

IEEE Xplore Digital Library

Interactive Wood Combustion for Botanical Tree Models

S. Pirk, M. Jarząbek, T. Hädrich, D. L. Michels, and W. Pałubicki.

ACM Transactions on Graphics (SIGGRAPH Asia 2017), ACM (2017).

We present a novel method for the combustion of botanical tree models. Tree models are represented as connected particles for the branching structure and a polygonal surface mesh for the combustion. Each particle stores biological and physical attributes that drive the kinetic behavior of a plant and the exothermic reaction of the combustion. Coupled with realistic physics for rods, the particles enable dynamic branch motions. We model material properties, such as moisture and charring behavior, and associate them with individual particles. The combustion is efficiently processed in the surface domain of the tree model on a polygonal mesh. A user can dynamically interact with the model by initiating fires and by inducing stress on branches. The flames realistically propagate through the tree model by consuming the available resources. Our method runs at interactive rates and supports multiple tree instances in parallel. We demonstrate the effectiveness of our approach through numerous examples and evaluate its plausibility against the combustion of real wood samples.

Featured in the conference's Technical Papers Trailer and by AAAS's EurekAlert!.

ACM Library Project Page Trailer EurekAlert!

Symbolic-Numeric Integration of the Dynamical Cosserat Equations

D. A. Lyakhov, V. P. Gerdt, A. G. Weber, and D. L. Michels.

Computer Algebra in Scientific Computing (CASC 2017), Springer (2017).

We devise a symbolic-numeric approach to the integration of the dynamical part of the Cosserat equations, a system of nonlinear partial differential equations describing the mechanical behavior of slender structures, like fibers and rods. This is based on our previous results on the construction of a closed form general solution to the kinematic part of the Cosserat system. Our approach combines methods of numerical exponential integration and symbolic integration of the intermediate system of nonlinear ordinary differential equations describing the dynamics of one of the arbitrary vector-functions in the general solution of the kinematic part in terms of the module of the twist vector-function. We present an experimental comparison with the well-established generalized α-method illustrating the computational efficiency of our approach for problems in structural mechanics.

Springer Link arXiv

A Stiffly Accurate Integrator for Elastodynamic Problems

D. L. Michels, V. T. Luan, and M. Tokman.

ACM Transactions on Graphics (SIGGRAPH 2017), ACM (2017).

We present a new integration algorithm for the accurate and efficient solution of stiff elastodynamic problems governed by the second-order ordinary differential equations of structural mechanics. Current methods have the shortcoming that their performance is highly dependent on the numerical stiffness of the underlying system that often leads to unrealistic behavior or a significant loss of efficiency. To overcome these limitations, we present a new integration method which is based on a mathematical reformulation of the underlying differential equations, an exponential treatment of the full nonlinear forcing operator as opposed to more standard partially implicit or exponential approaches, and the utilization of the concept of stiff accuracy which ensures that the efficiency of the simulations is significantly less sensitive to increased stiffness. As a consequence, we are able to tremendously accelerate the simulation of stiff systems compared to established integrators and significantly increase the overall accuracy. The advantageous behavior of this approach is demonstrated on a broad spectrum of complex examples like deformable bodies, textiles, bristles, and human hair. Our easily parallelizable integrator enables more complex and realistic models to be explored in visual computing without compromising efficiency.

Featured in the conference's Technical Papers Trailer and by UC News.

ACM Library Project Page Trailer UC News

Algorithmic Verification of Linearizability for Ordinary Differential Equations

D. A. Lyakhov, V. P. Gerdt, and D. L. Michels.

ACM International Symposium on Symbolic and Algebraic Computation (ISSAC 2017), ACM 2017.

For a nonlinear ordinary differential equation solved with respect to the highest order derivative and rational in the other derivatives and in the independent variable, we devise two algorithms to check if the equation can be reduced to a linear one by a point transformation of the dependent and independent variables. The first algorithm is based on a construction of the Lie point symmetry algebra and on the computation of its derived algebra. The second algorithm exploits the differential Thomas decomposition and allows not only to test the linearizability, but also to generate a system of nonlinear partial differential equations that determines the point transformation and the coefficients of the linearized equation. The implementation of both algorithms is discussed and their application is illustrated using several examples.

ACM SIGSAM Distinguished Paper Award.

ACM Library arXiv SIGSAM Awards

On Strongly Consistent Finite Difference Approximations to the Navier-Stokes Equations

D. A. Lyakhov, V. P. Gerdt, and D. L. Michels.

Foundations of Computational Mathematics (FoCM 2017), Symbolic Analysis Workshop (Poster), FoCM 2017.

The finite difference method is widely used for solving partial differential equations in the computational sciences. The decisive factor for its successful application is the quality of the underlying finite difference approximations. In this contribution, we present a computer algebra assisted approach to generate appropriate finite difference approximations to systems of polynomially nonlinear partial differential equations on regular Cartesian grids. The generated approximations satisfy the major quality criterion – strong consistency – which implies the preservation of fundamental algebraic properties of the system at the discrete level. This criterion admits a verification algorithm. We apply our approach to the Navier-Stokes equations and construct strongly consistent approximations. Moreover, we construct two approximations which are not only strongly consistent but also fully conservative.

Symbolic Analysis Workshop

Discrete Computational Mechanics for Stiff Phenomena

D. L. Michels and J. P. T. Mueller.

ACM SIGGRAPH Asia 2016, Course Notes, ACM (2016).

Many natural phenomena which occur in the realm of visual computing and computational physics, like the dynamics of cloth, fibers, fluids, and solids as well as collision scenarios are described by stiff Hamiltonian equations of motion, i.e. differential equations whose solution spectra simultaneously contain extremely high and low frequencies. This usually impedes the development of physically accurate and at the same time efficient integration algorithms. We present a straightforward computationally oriented introduction to advanced concepts from classical mechanics. We provide an easy to understand step-by-step introduction from variational principles over the Euler-Lagrange formalism and the Legendre transformation to Hamiltonian mechanics. Based on such solid theoretical foundations, we study the underlying geometric structure of Hamiltonian systems as well as their discrete counterparts in order to develop sophisticated structure preserving integration algorithms to efficiently perform high fidelity simulations.

ACM Library WWW

On the General Analytical Solution of the Kinematic Cosserat Equations

D. L. Michels, D. A. Lyakhov, V. P. Gerdt, Z. Hossain, I. H. Riedel-Kruse, and A. G. Weber.

Computer Algebra in Scientific Computing (CASC 2016), Springer (2016).

Based on a Lie symmetry analysis, we construct a closed form solution to the kinematic part of the (partial differential) Cosserat equations describing the mechanical behavior of elastic rods. The solution depends on two arbitrary analytical vector functions and is analytical everywhere except a certain domain of the independent variables in which one of the arbitrary vector functions satisfies a simple explicitly given algebraic relation. As our main theoretical result, in addition to the construction of the solution, we proof its generality. Based on this observation, a hybrid semi-analytical solver for highly viscous two-way coupled fluid-rod problems is developed which allows for the interactive high-fidelity simulations of flagellated microswimmers as a result of a substantial reduction of the numerical stiffness.

Springer Link Paper (PDF)