text:
# Fakultätskolloquium der Technischen Fakultät im WS 2017/18

• ### Die Kolloquien an den Instituten für Elektrotechnik und Informationstechnik sowie Materialwissenschaften:

Jeweils montags eine halbe Stunde vor Beginn der Vorträge, also um 16.45 Uhr, werden die Gastredner den Besuchern des Kolloquiums in einer zwanglosen Runde bei einer Tasse Kaffee in der "Eisdiele" (Eingangshalle Geb. D, neben dem "Aquarium") vorgestellt.

Ansprechpartner:  Daniel Johannsen (Tel. 0431-880-6068) dekanat@tf.uni-kiel.de

• ### Die Kolloquien am Institut für Informatik:

Alle Vorträge finden - soweit nicht anders angegeben - im Raum Ü2/K des Instituts für Informatik (Ludewig-Meyn-Str. 2, Vorbau des Mathematischen Seminars) freitags um 14 Uhr c.t. statt. 45 Minuten vor Vortragsbeginn stehen Tee und Kaffee bereit.

Ansprechpartner/innen: Geschäftszimmer des Instituts für Informatik (Tel. 0431 880-7270)aktuell@informatik.uni-kiel.de

• ### Wenn Sie die Einladungen per E-Mail erhalten möchten tragen Sie sich bitte in die Mailingliste ein.

Bitte achten Sie bei Sonderkolloquien auf die Zeit- und Raumangaben!

Nachfolgend alle Vortragstermine in chronologischer Abfolge

# Kolloquiumsvortrag, nn / am 02.10.2017

02.10.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Kolloquiumsvortrag, nn / am 06.10.2017

06.10.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 09.10.2017

09.10.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Kolloquiumsvortrag, nn / am 13.10.2017

13.10.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 16.10.2017

16.10.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Sonderkolloquium (INF), Vijay Ganesh, University of Waterloo, Kanada / am 17.10.2017

17.10.2017 von 14:00 bis 15:00

Institut für Informatik, Christian-Albrechts-Platz 4, 24118 Kiel

Titel: On The Unreasonable Effectiveness of Boolean SAT Solvers

Abstract: Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers routinely solve very large industrial SAT instances in relatively short periods of time. This phenomenon has stumped both theoreticians and practitioners since Boolean satisfiability is an NP-complete problem widely believed to be intractable. It is clear that these solvers somehow exploit the structure of real-world instances. However, to-date there have been few results that precisely characterize this structure or shed any light on why these SAT solvers are so efficient.

In this talk, I will present results that provide a deeper empirical understanding of why CDCL SAT solvers are so efficient, which may eventually lead to a complexity-theoretic result. Our results can be divided into two parts. First, I will talk about structural parameters that can characterize industrial instances and shed light on why they are easier to solve even though they may contain millions of variables compared to small crafted instances with hundreds of variables. Second, I will talk about internals of CDCL SAT solvers, and describe why they are particularly suited to solve industrial instances.

Brief Bio: Dr. Vijay Ganesh is an assistant professor at the University of Waterloo since 2012. Prior to that he was a research scientist at MIT, and completed his PhD in computer science from Stanford University in 2007. Vijay's primary area of research is the theory and practice of automated reasoning aimed at software engineering, formal methods, security, and mathematics. In this context he has led the development of many SAT/SMT solvers, most notably, STP, The Z3 string solver, MapleSAT, and MathCheck. He has also proved several decidability and complexity results relating to the SATisfiability problem for various mathematical theories. For his research, he has won over 20 awards including an ACM Test of Time Award at CCS 2016, two Google Faculty Research Awards in 2011 and 2013, and a Ten-Year Most Influential Paper Award at DATE 2008.

# Kolloquiumsvortrag, nn / am 20.10.2017

20.10.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 23.10.2017

23.10.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Kolloquiumsvortrag, nn / am 27.10.2017

27.10.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 30.10.2017

30.10.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Kolloquiumsvortrag, nn / am 03.11.2017

03.11.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 06.11.2017

06.11.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

# Kolloquiumsvortrag, nn / am 10.11.2017

10.11.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), Prof. Elisabetta Chicca, Uni Bielefeld / am 13.11.2017

13.11.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Learning in silico beyond STDP

Abstract: Synaptic plasticity empowers biological nervous systems with the ability to learn from experience and adjust to environmental changes. Such abilities are a must for artificial autonomous systems and therefore researchers have been devoting significant efforts to the understanding and modelling of plasticity mechanisms. In particular, the field of neuromorphic engineering focuses on the development of full-custom hybrid analog/digital electronic systems for the implementation of models of biological computation and learning in hardware. I will give a short historical overview of the most important plasticity circuits developed following the approach originally proposed by Carver Mead in the late eighties. Afterwards, I will present recent advancements in this field.

# Kolloquiumsvortrag, nn / am 17.11.2017

17.11.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), M.Sc. Jonas Sauter, Nuance Communications / am 20.11.2017

20.11.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Artificial Bandwidth Extension for Speech Signals Using Deep Neural Networks

Abstract: In mobile communication, the bandwidth of transferred speech signals is either narrow-band (300Hz – 3.4kHz) or wide-band (50Hz – 7kHz or higher). As the limitation to 3.4kHz degrades the speech quality and intelligibility, it is of great interest to artificially extend narrow-band speech signals to wide-band speech.

This talk presents a deep neural network (DNN) approach to artificial bandwidth extension with a focus on robustness in practical applications.

It is based on the source-filter model which decomposes the signal into two parts: an excitation signal and a spectral envelope. The excitation (source part) describes the fine spectral structure which consists of white noise for unvoiced speech and an impulse train for voiced speech. The spectral envelope (filter part) describes the coarse spectral structure, i.e. the formants or resonance frequencies that make up different phonemes.

While the extension of the excitation signal can be done with simple mathematical methods that do not introduce strong artifacts, the envelope is much more relevant for the quality of the reconstructed wide-band signal. That is why the wide-band envelope is estimated with DNNs in this approach, which are trained on a large speech corpus.

Short biography

Jonas Sautter studied Electrical Engineering, Information Technology and Computer Engineering at RWTH Aachen University, Germany. He received his Master of Science degree in 2016. The Master’s thesis with the title “Digital Robust Control for Active Noise Cancellation in Headphones and Hearing Aids” was composed at the Institute of Communication Systems at RWTH Aachen. Since November 2016, he is a PhD student at Nuance Communications in Ulm, supervised by Professor Gerhard Schmidt, Head of the Digital Signal Processing and System Theory group at Christian-Albrechts-Universität, Kiel.

# Kolloquiumsvortrag, nn / am 24.11.2017

24.11.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), Dr.-Ing. Vasudev Kanade Rajan / am 27.11.2017

27.11.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Digital Road Noise Cancellation System Through Active Noise Control

Abstract: The application of active noise cancellation in real-world has not been fully realized yet. From reducing environment noise through the usage of headphones, to engine noise on commercial jets there are a number of use cases. Each of these use case brings its own set of challenges which can be understood only through multi-disciplinary work. One such use case the the reduction of road noise in vehicles. Structure-borne road noise dominates the cabin of modern vehicles. Several road noise cancellation (RNC) prototype systems have been implemented and demonstrated. These systems are based mainly on analog sensors. The placement of these sensors has been so far been based on random optimization methods. In this talk I will talk about the challenges in developing a generic digital RNC system which includes problem analysis, sensor placement, and performance. An adaptive algorithm process the acceleration signals with high convergence and reaction time for various speed and surface ranges, in order to maintain high audible effects for the passengers. Several modern vehicle platforms are integrated with the digital RNC system with ANC microphone at the headliners and the standard audio loudspeaker setup in order to integrate the technology with the existing audio layout of the vehicle.

#### Short biography

Vasudev Kandade Rajan received Bachelors degree in Electronics and Communication from Visvesvaraya Technological University, Bangalore, India. He joined as Project Research Assistant in July 2008 in the Electrical Communication Engineering Dept, Indian Institute of Science, Bangalore. There he worked on performance management of IEEE 802.11 WLANs until Sept 2009. He then went to obtain his Masters degree (MSc.) in Digital Communications, 2011 and PhD degree in Signal Processing, 2017 from Universtiy of Kiel, Germany. Currently he is working in the R&D department of Harman Becker Automotive Systems GmbH, Straubing, Germany.

# Kolloquiumsvortrag, nn / am 01.12.2017

01.12.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), Dr. Andreas Bisplinghoff, Cisco / am 04.12.2017

04.12.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: From Long-Haul to Data-Center-Interconnect - Effiziente Signalverarbeitungsalgorithmen für Flexible Optische Netze

Abstract: First coherent optical communication systems, operating at 40Gbps, have been deployed in 2005. Since then, coherent optical technology has undergone remarkable development in the most recent years. Nowadays, state of the art products support line rates up to 400Gbps per wavelength. Next generation systems will primarily target for higher integration density but will presumably also reach line rates of 600Gbps and beyond.

With progress both in CMOS technology and of optical components, coherent optical transmission continuously pushes forward to highest reach for ultra-long haul applications as well as to highest capacity for shorter reach data-center interconnects. Both directions involve very specific requirements both on the capabilities of applied DSP algorithms and integration density of electrical and optical components.

Each new CMOS technology node facilitates the implementation of more sophisticated DSP algorithms. Many DSP components have undergone tremendous development during the most recent years, enabling coherent systems operating at highest transmission rates. Very efficient equalizer algorithms compensate for linear (CD, PMD) and non-linear (SPM, XPM) signal distortions, enhanced soft-decoded forward error correction schemes improve the noise tolerance, and with probabilistic constellation shaping performance will ultimately approach the Shannon limit.

This talk gives a high-level overview about state of the art DSP algorithms and most recent developments in coherent optical communication. It then discusses the balancing act to address the specific requirements of highest reach as well as highest capacity transmission within a single ASIC. Finally, some selected tradeoffs in algorithm and architecture optimization are shown by means of soft-decoded forward error correction as an example.

Bio: Andreas Bisplinghoff was born in Forchheim in 1984. He received the Dipl.-Ing. and Dr.-Ing. degrees both in electrical and electronic engineering from the Friedrich-Alexander University of Erlangen in 2009 and 2015, respectively.

From 2010 to 2013, he was a Research Assistant with the Institute of Microwaves and Photonics at the University of Erlangen. Since 2013 he has been a Hardware Engineer in Advanced Development with the Cisco Optical GmbH. His research interests include the development of slip-reduced carrier phase recovery techniques and of power-efficient forward error correction schemes for coherent optical communication. Andreas Bisplinghoff has broad experience in complexity-aware algorithm design, FPGA-based prototyping, and power-optimized ASIC implementation.

# Kolloquiumsvortrag, nn / am 08.12.2017

08.12.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (MaWi), Prof. Friedrich Frischknecht, Universität Heidelberg / am 11.12.2017

11.12.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Malaria transmission: new insights from in vivo imaging and materials science

Abstract: Malaria parasites are transmitted by mosquitoes and multiply to large numbers in red blood cells to cause disease. When taken up by mosquitoes the parasite develop in large cysts in their guts from where they emerge to colonize the salivary glands of the insect. From there the parasites are injected into the skin where they have to migrate to find a blood vessel. After entering the blood vessel the parasites first enter liver cells where they multiply without causing disease symptoms. In this seminar I will illuminate some of this curious biology using a set of different microscopy techniques, molecular genetics and biophysical approaches. We will see how parasites form within the cysts, how they leave the cysts, move within salivary glands and in the skin. Using laser tweezers we have measured the force they can produce and using micro-pillar arrays we have asked whether they adapted their shape in order to find the small blood capillaries into which they enter. For more info see: www.sporozoite.org

# Kolloquiumsvortrag, Dr. Patrick Totzke / Laboratory for Foundations of Computer Science at Edinburgh/ am 15.12.2017

15.12.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

Titel: Combined Objectives in Simple Stochastic Games

Abstract: SSG are turn-based, perfect information games where states are controlled by Adam, Eve or a randomized environment. The two opposing players compete to maximize/minimize the probability of a given winning condition (the objective of the game). I will outline a line of research that considers combinations of objectives classically studied for the verification of reactive systems, such as Parity, Mean-Payoff or limit-reward criteria. The aim is to determine under which conditions, to what extend, and with how much extra effort a player can achieve multiple objectives simultaneously. Time permitting, I will outline a recent result that exposes a subtle bug in the literature and shows how to fix it.

# Kolloquiumsvortrag (MaWi), PD Dr. Pavel Levkin, Karlsruhe Institute of Technology / am 18.12.2017

18.12.2017 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Abstract: Patterns of different surface properties are ubiquitous in nature and serve various important purposes. Desert beetles exploit superhydrophilic spots on their superhydrophobic back to collect water from the morning mist in the desert. Hydrophilic spots on a superhydrophobic surface of lichen plants allow them to uptake water, but also prevent the formation of water layers on the surface that could interfere with the discharge of lichen spores into the air. Superhydrophobic and omniphobic surfaces possess various unique properties including self-cleaning, liquid repellent and cell repellent properties. We are interested in creating precise two-dimensional micropatterns of apparently incompatible and opposite properties such as superhydrophobicity and superhydrophilicity or slippery and adhesive properties. To create such patterns we develop surface coatings with special wettabilities and photochemical surface functionalization strategies. Combining seemingly opposite properties in micropatterns leads to functionalities non-existent on the original homogeneous interfaces. For example, we showed that superhydrophobic-superhydrophilic patterned surfaces could be used to create patterns of cells, arrays of microdroplets suitable for high-throughput cell screenings, formation of arrays of hydrogel micropads or free-standing hydrogel particles with defined shapes for 3D cell culture. Patterned liquid-infused interfaces could be also used to form cell microarrays or arrays of isolated biofilm colonies for biofilm screenings.

# Kolloquiumsvortrag, nn / am 22.12.2017

22.12.2017 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag, nn / am 05.01.2018

05.01.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT) - muss leider entfallen - Prof. Frank Vollmer, University of Exeter / am 08.01.2018

08.01.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Sensing the Nanoscale with Optoplasmonics

Abstract: Nanophotonic device building blocks, such as optical nano/microcavities and plasmonic nanostructures, lie at the forefront of sensing and spectrometry of trace biological and chemical substances. My laboratory is developing a new class of nanophotonic architectures by combining optically resonant dielectric nano/microcavities with plasmonically resonant metal nanostructures to enable detection at the nanoscale with extraordinary sensitivity. Initial demonstrations include single-molecule detection and even single-ion sensing. The coupled photonic-plasmonic resonator system promises a leap forward in the nanoscale analysis of physical, chemical, and biological entities. I will review our work in this burgeoning field of optoplasmonic biosensors. I will also talk about our most recent advances in localising light at the nanoscale in disordered 2D photonic crystals.

1Department of Physics and Astronomy, Living Systems Institute, University of Exeter, EX44QD, Exeter, UK

E-mail: f.vollmer@exeter.ac.uk

CV: Frank Vollmer is a Professor of Biophysics at the Living Systems Institute at the University of Exeter. Prof Vollmer pioneers optical technology to study processes at the nanoscale. He held several appointments at leading US institutions including Instructor in Medicine at Harvard Medical School. Before moving to the LSI in 2016, he held the position of Research Group Leader at the Max Planck Institute for the Science of Light (DE). In 2017 Prof Vollmer was awarded the Royal Society Wolfson Research Merit Award.

References

# Kolloquiumsvortrag, nn / am 12.01.2018

12.01.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (MaWi), Prof. Weller, Uni Hamburg / am 15.01.2018

15.01.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Nanocrystals in Materials and Life Science Applications

Abstract:

Horst Weller,
Institut für Physikalische Chemie, Universität Hamburg, Fraunhofer-Zentrum für Angewandte Nanotechnologie (CAN), The Hamburg Centre for Ultrafast Imaging (CUI)

Nanocrystals are already used for many applications in technical products for every day life. The talk will describe actual developments such as quantum dots in display and lighting technology and ultra-hard nanocomposite materials. Modern aspects of particle synthesis will be discussed.
The key idea for using nanocrystals for biomedical diagnostics is to benefit from their outstanding physical properties in the visualization of biological events or malignant cells or tissues. This requires a special design of the ligand shell, which preserves the fluorescent, magnetic and plasmonic properties of the particles in the biological environment on one side and allows a specific targeting on the other. The lecture reports on different chemical approaches and describes factors determining the biological response on fully synthetic nanocrystals. We will highlight concepts based on PEGylation and show how small deviations in the ligand shell alter the behavior in biological environment substantially. Moreover, we will present combinatorial approaches for the functionalization of the nanocrystals with biological affinity molecules to improve targeting specificity and concepts to optimize the physical properties of the inorganic core to increase the sensitivity for the respective imaging techniques.

# Kolloquiumsvortrag, nn / am 19.01.2018

19.01.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), Prof. Martjin van den Heuvel, Brain Center Rudolf Magnu Utrecht / am 22.01.2018

22.01.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Exploring the human connectome

Abstract: Using network science as a general framework to study the network architecture of nervous system connectivity, more and more studies have highlighted the human and animal brain to display features of an efficient communication network. In my talk I will discuss potential general principles of wiring of connectome organization, principles conserved across species, and which may play an important role in general nervous system functioning. I will highlight findings that show connectomes to display cost-effective wiring, pronounced community structure, short communication relays, and the existence of richly connected 'hub regions'. I will discuss theories on how these themes of wiring may play a role in brain disorders, as well as establish a putative link between the micro- and macroscale organization of the human brain in health and disease.

# Kolloquiumsvortrag, nn / am 26.01.2018

26.01.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (MaWi), Prof. Kläui, Uni Mainz / am 29.01.2018

29.01.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Topological Spin Dynamics for GreenIT

Abstract: In our information-everywhere society IT is a major player for energy consumption. Novel spintronic
devices can play a role in the quest for GreenIT if they are stable and can transport and manipulate
spin with low power. Devices have been proposed, where switching by energy-efficient approaches,
such as spin-polarized currents is used [1], for which we develop new highly spin-polarized materials
and characterize the spin transport using THz spectroscopy [2]. Firstly to obtain ultimate stability, topological spin structures that emerge due to the
Dzyaloshinskii-Moriya interaction (DMI) at structurally asymmetric interfaces, such as chiral domain
walls and skyrmions with enhanced topological protection can be used [3-5]. We have investigated in
detail their dynamics and find that it is governed by the topology of their spin structures [3]. By
designing the materials, we can even obtain a skyrmion lattice phase as the ground state of the thin
films [4]. Secondly, for ultimately efficient spin manipulation, we use spin-orbit torques, that can transfer
more than 1ħ per electron by transferring not only spin but also orbital angular momentum. We
combine ultimately stable skyrmions with spin orbit torques into a skyrmion racetrack device [4],
where the real time imaging of the trajectories allows us to quantify the novel skyrmion Hall effect
[5]. Finally to obtain efficient spin transport, we study graphene and low damping ferro- and
antiferromagnetic insulators as spin conduits for long distance spin transport [6] and explore the
superfluid spin current regime in antiferromagnets [7]. We find that we can control magnonic spin
currents by a newly developed magnon spin valve device [8].

[1] Reviews: O. Boulle et al., Mater. Sci. Eng. R 72, 159
(2011); G. Finocchio et al., J. Phys. D: Appl. Phys. 49,
423001 (2016); A. Bisig et al., PRL 117, 277203 (2016)
[2] M. Jourdan et al., Nature Commun. 5, 3974 (2014);
Z. Jin et al., Nature Phys. 11, 761 (2015).
[3] F. Büttner et al., Nature Phys. 11, 225 (2015).
[4] S. Woo et al, Nature Mater. 15, 501 (2016).
[5] K. Litzius et al., Nature Phys. 13, 170 (2017).
[6] A. Kehlberger et al., Phys. Rev. Lett. 115, 096602 (2015);
S. Geprägs et al., Nature Commun. 7, 10452 (2016).
[7] Y. Tserkovnyak and M. Kläui, arxiv:1707.01082
[8] J. Cramer et al., arxiv:1706.07592

# Kolloquiumsvortrag (INF) Arindam Khan, TU München / am 02.02.2018

02.02.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

Titel: Approximating Geometric Knapsack via L-packings

Abstract: We study the two-dimensional geometric knapsack problem (2DK), a
geometric variant of the classical knapsack problem. In this problem, we
are given a set of axis-aligned rectangular items, each one with an
associated profit, and an axis-aligned square knapsack. The goal is to
find a (non-overlapping) packing of a maximum profit subset of items
inside the knapsack without rotating items. This is a very well-studied
optimization problem and finds applications in scheduling, memory
approximation factor for this problem (even just in the cardinality
case) is $2+\epsilon$ [Jansen and Zhang, SODA 2004].

After more than a decade, in this paper we break the 2-approximation
barrier, achieving a polynomial-time $17/9+\epsilon<1.89$ approximation,
which improves to $558/325+\epsilon<1.72$ in the cardinality case. We
also consider the variant of the problem with rotations (2DKR), where
the items can be rotated by $90$ degrees. Also, in this case, the
best-known polynomial-time approximation factor (even for the
cardinality case) is $2+\epsilon$ [Jansen and Zhang, SODA 2004].
Exploiting part of the machinery developed for 2DK plus a few additional
ideas, we obtain a polynomial-time $3/2+\epsilon$-approximation for
2DKR, which improves to $4/3+\epsilon$ in the cardinality case (joint
work with Waldo Galvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore
Ingala and Andreas Wiese.).

Bio: Arindam Khan is a postdoc in Lehrstuhl für Theoretische Informatik
at Technische Universität München. His research areas include
approximation algorithms, online algorithms and computational geometry.
He has obtained his PhD in Algorithms, Combinatorics and Optimization
(ACO) from Georgia Institute of Technology, Atlanta, USA under Prof.
Prasad Tetali. Previously he has been a research intern in Theory group,
Microsoft Research Redmond and Microsoft Research Silicon Valley USA, a
visiting researcher at Simons Institute, Berkeley, USA; a blue scholar
in IBM Research India and a researcher at IDSIA, Lugano, Switzerland.

# Kolloquiumsvortrag (MaWi), Frau Dr. Berit Zeller-Plumdorf, Helmholtz Zentrum Geesthacht / am 05.02.2018

05.02.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Imaging and image-based modelling of biological and material systems

Abstract: Synchrotron radiation-based computed tomography (SRμCT) is a powerful tool for high-resolution imaging of materials. Whilst it traditionally depends on the X-ray attenuation by material components with high Z-numbers, it can be enhanced to enable imaging of biological soft tissues and other low-attenuation materials through propagation-based phase contrast. Due to the available high photon flux it is also possible to perform in situ testing, e.g. of material corrosion or mechanical loading experiments. In combination with image-based mathematical modelling, SRμCT enables the correlation between morphological and/or structural material measures and their function. In this presentation, showcases will be presented where SRμCT and image-based modelling have successfully been used to this end. These showcases include the assessment of osseointegration and in vitro degradation of biodegradable implants, the computational analysis of oxygenation in mouse muscle and the corrosion of steel embedded in concrete in aqueous solutions.

# Kolloquiumsvortrag, nn / am 09.02.2018

09.02.2018 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Straße 2, 24118 Kiel, Raum: Übungsraum 2/K

# Kolloquiumsvortrag (ET&IT), Dr. Timm Faulwasser, Karlsruhe Institute of Technology / am 12.02.2018

12.02.2018 von 17:15 bis 18:00

Institute Ostufer, Geb. D, "Aquarium", Kaiserstr. 2, 24143 Kiel

Titel: Recent Progress on Distributed and Stochastic Optimization for Power Systems

Abstract: The increasing need for the de-carbonization of energy supply calls for new operational methods for power systems. In this context, tailored system and control approaches are pivotal- The specific challenges include the consideration of volatile renewable generation, uncertain forecasts thereof, and highly nonlinear system behavior.

In this talk, we focus on the so-called Optimal Power Flow (OPF) problem, which refers to a class of large-scale non-convex steady-state optimization problems frequently arising in power systems. For example, OPF problems provide optimal set points for power dispatch that satisfy the power flow equations and technical limitations such as generation and/or transmission limits. However, OPF problems are highly non-convex and subject to considerable uncertainties, which includes forecasts of renewable generation and household consumption, line parameters and grid topology.

After a concise problem statement, we provide an overview of the state of the art techniques to considering uncertainties in OPF problems and their bottlenecks. Moreover, we will discuss the concept of Polynomial Chaos Expansions (PCE) which allows to consider non-Gaussian uncertainties in OPF problems. PCE builds upon a series expansion of random-variables. We will present recent results on PCE for convex DC-OPF problems and non-convex AC-OPF problems [1, 2]. Moreover, we will comment on the quantification of PCE truncation errors [3].

Due to their large-scale nature, the distributed solution of OPF problems is subject to considerable research efforts. Thus, we will also comment on our recent results on the distributed solution of OPF problems [4].

References

[1] Mühlpfordt, T.; Faulwasser, T.; Roald, L. & Hagenmeyer, V. Solving optimal power flow with non-Gaussian uncertainties via polynomial chaos expansion. 56th IEEE Conference on Decision and Control, 2017. To appear.

[2] Mühlpfordt, T.; Faulwasser, T. & Hagenmeyer, V. Solving stochastic AC power flow via polynomial chaos expansion. IEEE International Conference on Control Applications, 2016, 70-76.

[3] Mühlpfordt, T.; Findeisen, R.; Hagenmeyer, V. & Faulwasser, T. Comments on Quantifying Truncation Errors for Polynomial Chaos Expansions. arXiv:1708.07655.

[4] Engelmann, A.; Mühlpfordt, T.; Jiang, Y.; Houska, B. & Faulwasser, T. Distributed AC optimal power flow using ALADIN. 20th IFAC World Congress, 2017.

Bio Sketch

Timm Faulwasser has studied Engineering Cybernetics at the University Stuttgart, with majors in systems and control and philosophy, where he graduated 2006. In 2007 he joined the group of Rolf Findeisen at the Institute of Automation Engineering at the Otto-von-Guericke University Magdeburg, Germany. From 2008-2012 he was a member of the International Max Planck Research School for Analysis, Design and Optimization in Chemical and Biochemical Process Engineering Magdeburg. In 2012 he obtained his PhD (with distinction) from Faculty of Electrical Engineering and Information Engineering, Otto-von-Guericke University Magdeburg, Germany. 2013-2016 he was with the Laboratoire d’Automatique, Ecole Polytechnique Fédérale de Lausanne, Switzerland. Since April 2015, he is with the Institute for Applied Informatics at the Karlsruhe Institute for Technology, where he leads the Optimization and Control Group.

His main research interests are optimization-based and predictive control of nonlinear systems with applications in energy systems, mechatronics/robotics, physics, process systems engineering and climate economics.


text:
E. New Year Tree Decorations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Due to atheistic Soviet past, Christmas wasn't officially celebrated in Russia for most of the twentieth century. As a result, the Russian traditions for Christmas and New Year mixed into one event celebrated on the New Year but including the tree, a Santa-like 'Grandfather Frost', presents and huge family reunions and dinner parties all over the country. Bying a Tree at the New Year and installing it in the house is a tradition. Usually the whole family decorates the tree on the New Year Eve. We hope that Codeforces is a big and loving family, so in this problem we are going to decorate a tree as well.

So, our decoration consists of n pieces, each piece is a piece of colored paper, its border is a closed polyline of a special shape. The pieces go one by one as is shown on the picture. The i-th piece is a polyline that goes through points: (0, 0), (0, y0), (1, y1), (2, y2), ..., (k, yk), (k, 0). The width of each piece equals k.

The figure to the left shows the decoration, the figure to the right shows the individual pieces it consists of.

The piece number 1 (shown red on the figure) is the outer piece (we see it completely), piece number 2 (shown yellow) follows it (we don't see it completely as it is partially closed by the first piece) and so on. The programmers are quite curious guys, so the moment we hung a decoration on the New Year tree we started to wonder: what area of each piece can people see?

Input

The first line contains two integers, n and k (1 ≤ n, k ≤ 300). Each of the following n lines contains k + 1 integers — the description of the polyline. If the i-th line contains ontegers yi, 0, yi, 1, ..., yi, k, that means that the polyline of the i-th piece goes through points (0, 0), (0, yi, 0), (1, yi, 1), (2, yi, 2), ..., (k, yi, k), (k, 0) (1 ≤ yi, j ≤ 1000).

Output

Print n real numbers — for each polyline, the area of its visible part.

The answer will be considered correct if its relative or absolute error do not exceed 10 - 4.

Examples
Input
2 22 1 21 2 1
Output
3.0000000000000.500000000000
Input
1 11 1
Output
1.000000000000
Input
4 12 77 25 56 4
Output
4.5000000000001.2500000000000.0500000000000.016666666667

format: plain


text:
$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Skills to Develop

• Simplify radical expressions using the product and quotient rule for radicals.

An algebraic expression that contains radicals is called a radical expression14. We use the product and quotient rules to simplify them.

Example $$\PageIndex{1}$$:

Simplify: $$\sqrt [ 3 ] { 27 x ^ { 3 } }$$.

Solution

Use the fact that $$\sqrt [ n ] { a ^ { n } } = a$$ when $$n$$ is odd.

\begin{aligned} \sqrt [ 3 ] { 27 x ^ { 3 } } & = \sqrt [ 3 ] { 3 ^ { 3 } \cdot x ^ { 3 } }\quad\quad \color{Cerulean} { Apply \:the\: product \:rule\: for\: radicals.} \\ & = \sqrt [ 3 ] { 3 ^ { 3 } } \cdot \sqrt [ 3 ] { x ^ { 3 } }\quad \color{Cerulean} { Simplify. } \\ & = 3 \cdot x \\ & = 3 x \end{aligned}

$$3x$$

Example $$\PageIndex{2}$$:

Simplify: $$\sqrt [ 4 ] { 16 y ^ { 4 } }$$.

Solution

Use the fact that $$\sqrt [ n ] { a ^ { n } } = | a |$$ when $$n$$ is even.

\begin{aligned} \sqrt [ 4 ] { 16 y ^ { 4 } } & = \sqrt [ 4 ] { 2 ^ { 4 } y ^ { 4 } }\quad\quad\:\:\: \color{Cerulean} { Apply\: the\: product\: rule\: for\: radicals.} \\ & = \sqrt [ 4 ] { 2 ^ { 4 } } \cdot \sqrt [ 4 ] { y ^ { 4 } }\:\:\:\: \color{Cerulean} { Simplify. } \\ & = 2 \cdot | y | \\ & = 2 | y | \end{aligned}

Since $$y$$ is a variable, it may represent a negative number. Thus we need to ensure that the result is positive by including the absolute value.

$$2 | y |$$

Note

Typically, at this point in algebra we note that all variables are assumed to be positive. If this is the case, then $$y$$ in the previous example is positive and the absolute value operator is not needed. The example can be simplified as follows.

\begin{aligned} \sqrt [ 4 ] { 16 y ^ { 4 } } & = \sqrt [ 4 ] { 2 ^ { 4 } y ^ { 4 } } \\ & = \sqrt [ 4 ] { 2 ^ { 4 } } \cdot \sqrt [ 4 ] { y ^ { 4 } } \\ & = 2 y \end{aligned}

In this section, we will assume that all variables are positive. This allows us to focus on calculating $$n$$th roots without the technicalities associated with the principal $$n$$th root problem. For this reason, we will use the following property for the rest of the section,

$$\sqrt [ n ] { a ^ { n } } = a , \quad \text { if } a \geq 0 \quad \color{Cerulean}{nth \:root}$$

When simplifying radical expressions, look for factors with powers that match the index.

Example $$\PageIndex{3}$$:

Simplify: $$\sqrt { 12 x ^ { 6 } y ^ { 3 } }$$.

Solution

Begin by determining the square factors of $$12, x^{ 6}$$ , and $$y^{ 3}$$.

$$\left. \begin{array} { l } { 12 = \color{Cerulean}{2 ^ { 2} }\color{black}{ \cdot} 3 } \\ { x ^ { 6 } = \color{Cerulean}{\left( x ^ { 3 } \right) ^ { 2 } }} \\ { y ^ { 3 } = \color{Cerulean}{y ^ { 2} }\color{black}{ \cdot} y } \end{array} \right\} \quad\color{Cerulean}{Square\:factors}$$

Make these substitutions, and then apply the product rule for radicals and simplify.

\begin{aligned} \sqrt { 12 x ^ { 6 } y ^ { 3 } } & = \sqrt { \color{Cerulean}{2 ^ { 2} }\color{black}{ \cdot} 3 \cdot \color{Cerulean}{\left( x ^ { 3 } \right) ^ { 2 }}\color{black}{ \cdot}\color{Cerulean}{ y ^ { 2} }\color{black}{ \cdot} y } \quad\quad\quad\quad\:\color{Cerulean} { Apply\:the\: product \:rule\: for\: radicals. } \\ & = \sqrt { 2 ^ { 2 } } \cdot \sqrt { \left( x ^ { 3 } \right) ^ { 2 } } \cdot \sqrt { y ^ { 2 } } \cdot \sqrt { 3 y } \quad\color{Cerulean} { Simplify. } \\ & = 2 \cdot x ^ { 3 } \cdot y \cdot \sqrt { 3 y } \\ & = 2 x ^ { 3 } y \sqrt { 3 y } \end{aligned}

$$2 x ^ { 3 } y \sqrt { 3 y }$$

Example $$\PageIndex{4}$$:

Simplify: $$\sqrt { \frac { 18 a ^ { 5 } } { b ^ { 8 } } }$$.

Solution

Begin by determining the square factors of $$18$$, $$a^{5}$$, and $$b^{8}$$.

$$\left. \begin{array} { l } { 18 = 2 \cdot \color{Cerulean}{3 ^ { 2} } } \\ { a ^ { 5 } = a ^ { 2 } \cdot a ^ { 2 } \cdot a = \color{Cerulean}{\left( a ^ { 2 } \right) ^ { 2 }}\color{black}{ \cdot} a } \\ { b ^ { 8 } = b ^ { 4 } \cdot b ^ { 4 } \quad\:\:= \color{Cerulean}{\left( b ^ { 4 } \right) ^ { 2 }} } \end{array}\quad \right\}\quad\color{Cerulean}{Square\:factors}$$

Make these substitutions, apply the product and quotient rules for radicals, and then simplify.

\begin{aligned} \sqrt { \frac { 18 a ^ { 5 } } { b ^ { 8 } } } & = \sqrt { \frac { 2 \cdot \color{Cerulean}{3 ^ { 2} }\color{black}{ \cdot}\color{Cerulean}{ \left( a ^ { 2 } \right) ^ { 2 }}\color{black}{ \cdot} a } { \color{Cerulean}{\left( b ^ { 4 } \right) ^ { 2 } } }}\quad\quad\color{Cerulean}{Apply\:the\:product\:and\:quotient\:rule\:for\:radicals.} \\ & = \frac { \sqrt { 3 ^ { 2 } } \cdot \sqrt { \left( a ^ { 2 } \right) ^ { 2 } } \cdot \sqrt { 2 a } } { \sqrt { \left( b ^ { 4 } \right) ^ { 2 } } }\quad \color{Cerulean}{Simplify.} \\ & = \frac { 3 a ^ { 2 } \sqrt { 2 a } } { b ^ { 4 } } \end{aligned}

$$\frac { 3 a ^ { 2 } \sqrt { 2 a } } { b ^ { 4 } }$$

Example $$\PageIndex{5}$$:

Simplify: $$\sqrt [ 3 ] { 80 x ^ { 5 } y ^ { 7 } }$$.

Solution

Begin by determining the cubic factors of $$80 , x ^ { 5 }$$, and $$y^{7}$$.

$$\left. \begin{array} { l } { 80 = 2 ^ { 4 } \cdot 5 = \color{Cerulean}{2 ^ { 3} }\color{black}{ \cdot} 2 \cdot 5 } \\ { x ^ { 5 } = \color{Cerulean}{x ^ { 3 }}\color{black}{ \cdot} x ^ { 2 } } \\ { y ^ { 7 } = y ^ { 6 } \cdot y =\color{Cerulean}{ \left( y ^ { 2 } \right) ^ { 3 } }\color{black}{\cdot} y } \end{array} \quad\right\}\quad\color{Cerulean}{Cubic\:factors}$$

Make these substitutions, and then apply the product rule for radicals and simplify.

\begin{aligned} \sqrt [ 3 ] { 80 x ^ { 5 } y ^ { 7 } } & = \sqrt [ 3 ] { \color{Cerulean}{2 ^ { 3} }\color{black}{ \cdot} 2 \cdot 5 \cdot \color{Cerulean}{x ^ { 3 }}\color{black}{ \cdot} x ^ { 2 } \cdot \color{Cerulean}{\left( y ^ { 2 } \right) ^ { 3 }}\color{black}{ \cdot} y } \\ & = \sqrt [ 3 ] { \color{Cerulean}{2 ^ { 3} } } \color{black}{\cdot} \sqrt [ 3 ] { \color{Cerulean}{x ^ { 3 }} }\color{black}{ \cdot} \sqrt [ 3 ] { \color{Cerulean}{\left( y ^ { 2 } \right) ^ { 3 } } }\color{black}{\cdot} \sqrt [ 3 ] { 2 \cdot 5 \cdot x ^ { 2 } \cdot y } \\ & = 2 \cdot x y ^ { 2 } \cdot \sqrt [ 3 ] { 10 x ^ { 2 } y } \\ & = 2 x y ^ { 2 } \sqrt [ 3 ] { 10 x ^ { 2 } y } \end{aligned}

$$2 x y ^ { 2 } \sqrt [ 3 ] { 10 x ^ { 2 } y }$$

Example $$\PageIndex{6}$$:

Simplify: $$\sqrt [ 3 ] { \frac { 9 x ^ { 6 } } { y ^ { 3 } z ^ { 9 } } }$$.

Solution

The coefficient $$9 = 3^{2}$$, and thus does not have any perfect cube factors. It will be left as the only remaining radicand because all of the other factors are cubes, as illustrated below:

$$\left. \begin{array} { l } { x ^ { 6 } = \left( x ^ { 2 } \right) ^ { 3 } } \\ { y ^ { 3 } = ( y ) ^ { 3 } } \\ { z ^ { 9 } = \left( z ^ { 3 } \right) ^ { 3 } } \end{array} \quad\right\}\quad\color{Cerulean}{Cubic\:factors}$$

Replace the variables with these equivalents, apply the product and quotient rules for radicals, and then simplify.

\begin{aligned} \sqrt [ 3 ] { \frac { 9 x ^ { 6 } } { y ^ { 3 } z ^ { 9 } } } & = \sqrt [ 3 ] { \frac { 9 \cdot \left( x ^ { 2 } \right) ^ { 3 } } { y ^ { 3 } \cdot \left( z ^ { 3 } \right) ^ { 3 } } } \\ & = \frac { \sqrt [ 3 ] { 9 } \cdot \sqrt [ 3 ] { \left( x ^ { 2 } \right) ^ { 3 } } } { \sqrt [ 3 ] { y ^ { 3 } } \cdot \sqrt [ 3 ] { \left( z ^ { 3 } \right) ^ { 3 } } } \\ & = \frac{\sqrt[3]{9} \:\cdot\:x^{2} }{y\:\cdot\:z^{3}}\\&= \frac{x^{2}\:\sqrt[3]{9}}{yz^{3}}\end{aligned}

$$\frac { x ^ { 2 } \sqrt [ 3 ] { 9 } } { y z ^ { 3 } }$$

Example $$\PageIndex{7}$$:

Simplify: $$\sqrt [ 4 ] { 81 a ^ { 4 } b ^ { 5 } }$$.

Solution

Determine all factors that can be written as perfect powers of $$4$$. Here, it is important to see that $$b^{5} = b^{4} ⋅ b$$. Hence the factor $$b$$ will be left inside the radical.

\begin{aligned} \sqrt [ 4 ] { 81 a ^ { 4 } b ^ { 5 } } & = \sqrt [ 4 ] { 3 ^ { 4 } \cdot a ^ { 4 } \cdot b ^ { 4 } \cdot b } \\ & = \sqrt [ 4 ] { 3 ^ { 4 } } \cdot \sqrt [ 4 ] { a ^ { 4 } } \cdot \sqrt [ 4 ] { b ^ { 4 } } \cdot \sqrt [ 4 ] { b } \\ & = 3 \cdot a \cdot b \cdot \sqrt [ 4 ] { b } \\ & = 3 a b \sqrt [ 4 ] { b } \end{aligned}

$$3 a b \sqrt [ 4 ] { b }$$

Example $$\PageIndex{8}$$:

Simplify: $$\sqrt [ 5 ] { - 32 x ^ { 3 } y ^ { 6 } z ^ { 5 } }$$.

Solution

Notice that the variable factor $$x$$ cannot be written as a power of $$5$$ and thus will be left inside the radical. In addition, $$y^{6} = y^{5} ⋅ y$$; the factor $$y$$ will be left inside the radical as well.

\begin{aligned} \sqrt [ 3 ] { - 32 x ^ { 3 } y ^ { 6 } z ^ { 5 } } & = \sqrt [ 5 ] { \color{Cerulean}{( - 2 ) ^ { 5 } }\color{black}{\cdot} x ^ { 3 } \cdot\color{Cerulean}{ y ^ { 5} }\color{black}{ \cdot} y \cdot \color{Cerulean}{z ^ { 5} } } \\ & = \sqrt [ 5 ] {\color{Cerulean}{ ( - 2 ) ^ { 5 } }} \color{black}{\cdot} \sqrt [ 5 ] { \color{Cerulean}{y ^ { 5 }} }\color{black}{ \cdot} \sqrt [ 5 ] { \color{Cerulean}{z ^ { 5} } }\color{black}{ \cdot} \sqrt [ 5 ] { x ^ { 3 } \cdot y } \\ & = - 2 \cdot y \cdot z \cdot \sqrt [ 5 ] { x ^ { 3 } \cdot y } \\ & = - 2 y z \sqrt [ 5 ] { x ^ { 3 } y } \end{aligned}

$$- 2 y z \sqrt [ 5 ] { x ^ { 3 } y }$$

Tip: To simplify finding an $$n$$th root, divide the powers by the index.

\begin{aligned} \sqrt { a ^ { 6 } } = a ^ { 3 } , & \text { which is } a ^ { 6 \div 2 } = a ^ { 3 } \\ \sqrt [ 3 ] { b ^ { 6 } } = b ^ { 2 } , & \text { which is } b ^ { 6 \div 3 } = b ^ { 2 } \\ \sqrt[6]{c^{6}} = c\:\:, &\: \text{which is} \:{c^{6\div 6} = c^{1}} \end{aligned}

If the index does not divide into the power evenly, then we can use the quotient and remainder to simplify. For example,

\begin{aligned} \sqrt { a ^ { 5 } }& = a ^ { 2 } \cdot \sqrt { a } , \text { which is } a ^ { 5 \div 2 } = a ^ { 2 r 1 } \\ \sqrt [ 3 ] { b ^ { 5 } }& = b \cdot \sqrt [ 3 ] { b ^ { 2 } } , \text { which is } b ^ { 5 \div 3 } = b ^ { 1 r 2 } \\ \sqrt[5]{c^{14}} &= c^{2} \cdot\sqrt[5]{c^{4}}, \text{which is} \:c^{14\div 5} = c^{2r4} \end{aligned}

The quotient is the exponent of the factor outside of the radical, and the remainder is the exponent of the factor left inside the radical.

Exercise $$\PageIndex{1}$$

Simplify: $$\sqrt [ 3 ] { 162 a ^ { 7 } b ^ { 5 } c ^ { 4 } }$$.

$$3 a ^ { 2 } b c \sqrt [ 3 ] { 6 a b ^ { 2 } c }$$

Formulas often consist of radical expressions. For example, the period of a pendulum, or the time it takes a pendulum to swing from one side to the other and back, depends on its length according to the following formula.

$$T = 2 \pi \sqrt { \frac { L } { 32 } }$$

Here $$T$$ represents the period in seconds and $$L$$ represents the length in feet of the pendulum.

Example $$\PageIndex{9}$$:

If the length of a pendulum measures $$1 \frac{1}{2}$$ feet, then calculate the period rounded to the nearest tenth of a second.

Solution

Substitute $$1 \frac{1}{2} = \frac{3}{2}$$ for $$L$$ and then simplify.

\begin{aligned} T & = 2 \pi \sqrt { \frac { L } { 32 } } \\ & = 2 \pi \sqrt { \frac { \frac{3}{2} } { 32 } } \\ & = 2 \pi \sqrt { \frac { 3 } { 2 } \cdot \frac { 1 } { 32 } } \quad\color{Cerulean}{Apply\:the\:quotient\:rule\:for\:radicals.} \\ & = 2 \pi \frac { \sqrt { 3 } } { \sqrt { 64 } }\quad\quad\:\:\:\color{Cerulean}{Simplify.} \\ & = \frac { \pi \sqrt { 3 } } { 4 } \approx 1.36 \end{aligned}

The period is approximately $$1.36$$ seconds.

Frequently you need to calculate the distance between two points in a plane. To do this, form a right triangle using the two points as vertices of the triangle and then apply the Pythagorean theorem. Recall that the Pythagorean theorem states that if given any right triangle with legs measuring $$a$$ and $$b$$ units, then the square of the measure of the hypotenuse $$c$$ is equal to the sum of the squares of the legs: $$a^{2} + b^{2} = c^{2}$$. In other words, the hypotenuse of any right triangle is equal to the square root of the sum of the squares of its legs.

Example $$\PageIndex{10}$$:

Find the distance between $$(-5,3)$$ and $$(1,1)$$.

Solution

Form a right triangle by drawing horizontal and vertical lines though the two points. This creates a right triangle as shown below:

The length of leg $$b$$ is calculated by finding the distance between the $$x$$-values of the given points, and the length of leg $$a$$ is calculated by finding the distance between the given $$y$$-values.

$$\begin{array} { l } { a = 3 - 1 = 2 \text { units } } \\ { b = 1 - ( - 5 ) = 1 + 5 = 6 \text { units } } \end{array}$$

Next, use the Pythagorean theorem to find the length of the hypotenuse.

\begin{aligned} c & = \sqrt { 2 ^ { 2 } + 6 ^ { 2 } } \\ & = \sqrt { 4 + 36 } \\ & = \sqrt { 40 } \\ & = \sqrt { 4 \cdot 10 } \\ & = 2 \sqrt { 10 } \text { units } \end{aligned}

The distance between the two points is $$2 \sqrt{10}$$ units.

Generalize this process to produce a formula that can be used to algebraically calculate the distance between any two given points.

Given two points, $$\left( x _ { 1 } , y _ { 1 } \right)$$ and $$\left( x _ { 2 } , y _ { 2 } \right)$$ the distance, $$d|), between them is given by the distance formula15, \(d = \sqrt { \left( x _ { 2 } - x _ { 1 } \right) ^ { 2 } + \left( y _ { 2 } - y _ { 1 } \right) ^ { 2 } }$$.

Example $$\PageIndex{11}$$:

Calculate the distance between $$(-4,7)$$ and $$(2,1)$$.

Solution

Use the distance formula with the following points.

$$\begin{array} { l } { \left( x _ { 1 } , y _ { 1 } \right) \left( x _ { 2 } , y _ { 2 } \right) } \\ { (\color{Cerulean}{ - 4}\color{black}{,}\color{OliveGreen}{7}\color{black}{ )} \quad ( \color{Cerulean}{2}\color{black}{,}\color{OliveGreen}{1}\color{black}{ )} } \end{array}$$

It is a good practice to include the formula in its general form before substituting values for the variables; this improves readability and reduces the probability of making errors.

\begin{aligned} d & = \sqrt { \left( x _ { 2 } - x _ { 1 } \right) ^ { 2 } + \left( y _ { 2 } - y _ { 1 } \right) ^ { 2 } } \\ & = \sqrt { ( \color{Cerulean}{2}\color{black}{ -} ( \color{Cerulean}{- 4}\color{black}{ )} ) ^ { 2 } + ( \color{OliveGreen}{1}\color{black}{ -}\color{OliveGreen}{ 7}\color{black}{ )} ^ { 2 } } \\ & = \sqrt { ( 2 + 4 ) ^ { 2 } + ( 1 - 7 ) ^ { 2 } } \\ & = \sqrt { ( 6 ) ^ { 2 } + ( - 6 ) ^ { 2 } } \\ & = \sqrt { 72 }\\ & = \sqrt{36\cdot2} \\ & = 6 \sqrt { 2 } \end{aligned}

The distance between the two points is $$6\sqrt{2}$$ units.

Example $$\PageIndex{12}$$:

Do the three points $$( 2 , - 1 ) , ( 3,2 )$$, and $$(8,-3)$$ form a right triangle?

Solution

The Pythagorean theorem states that having side lengths that satisfy the property $$a^{2} + b^{2}= c^{2}$$ is a necessary and sufficient condition of right triangles. In other words, if you can show that the sum of the squares of the leg lengths of the triangle is equal to the square of the length of the hypotenuse, then the triangle must be a right triangle. First, calculate the length of each side using the distance formula.

Geometry Calculation

Figure 5.2.4

Points: $$(2,-1)$$ and $$(8,-3)$$

$$\begin{array} { l } { a = \sqrt { ( 8 - 2 ) ^ { 2 } + [ - 3 - ( - 1 ) ] ^ { 2 } } } \\ { = \sqrt { ( 6 ) ^ { 2 } + ( - 3 + 1 ) ^ { 2 } } } \\ { = \sqrt { 36 + ( - 2 ) ^ { 2 } } } \\ { = \sqrt { 36 + 4 } } \\ { = \sqrt{40} } \\ { = 2 \sqrt { 10 } } \end{array}$$

Points: $$(2,-1)$$ and $$(3,2)$$

$$\begin{array} { l } { b = \sqrt { ( 3 - 2 ) ^ { 2 } + [ 2 - ( - 1 ) ] ^ { 2 } } } \\ { = \sqrt { ( 1 ) ^ { 2 } + ( 2 + 1 ) ^ { 2 } } } \\ = \sqrt{1+ (3)^{2}}\\{ = \sqrt { 1 + 9 } } \\ { = \sqrt { 10 } } \end{array}$$

Figure 5.2.6

Points: $$(3,2)$$ and $$(8,-3)$$

$$\begin{array} { l } { c = \sqrt { ( 8 - 3 ) ^ { 2 } + ( - 3 - 2 ) ^ { 2 } } } \\ { = \sqrt { ( 5 ) ^ { 2 } + ( - 5 ) ^ { 2 } } } \\ { = \sqrt { 25 + 25 } } \\ { = \sqrt { 50 } } \\ { = 5 \sqrt { 2 } } \end{array}$$

Table 5.2.1

Now we check to see if $$a ^ { 2 } + b ^ { 2 } = c ^ { 2 }$$.

\begin{aligned} a ^ { 2 } + b ^ { 2 } & = c ^ { 2 } \\ ( 2 \sqrt { 10 } ) ^ { 2 } + ( \sqrt { 10 } ) ^ { 2 } &= ( 5 \sqrt { 2 } ) ^ { 2 } \\ 4 ( \sqrt { 10 } ) ^ { 2 } + ( \sqrt { 10 } ) ^ { 2 } & = 25 ( \sqrt { 2 } ) ^ { 2 } \\ 4 \cdot 10 + 10 &= 25 \cdot 2 \\ 50 &= 50 \:\:\color{Cerulean}{✓}\end{aligned}

Yes, the three points form a right triangle.

Exercise $$\PageIndex{2}$$

The speed of a vehicle before the brakes were applied can be estimated by the length of the skid marks left on the road. On wet concrete, the speed $$v$$ in miles per hour can be estimated by the formula $$v = 2 \sqrt { 3 d }$$, where $$d$$ represents the length of the skid marks in feet. Estimate the speed of a vehicle before applying the brakes if the skid marks left behind measure $$27$$ feet. Round to the nearest mile per hour.

$$18$$ miles per hour

## Key Takeaways

• To simplify a radical expression, look for factors of the radicand with powers that match the index. If found, they can be simplified by applying the product and quotient rules for radicals, as well as the property $$\sqrt [ n ] { a ^ { n } } = a$$, where $$a$$ is nonnegative.
• A radical expression is simplified if its radicand does not contain any factors that can be written as perfect powers of the index.
• We typically assume that all variable expressions within the radical are nonnegative. This allows us to focus on simplifying radicals without the technical issues associated with the principal $$n$$th root. If this assumption is not made, we will ensure a positive result by using absolute values when simplifying radicals with even indices.

Exercise $$\PageIndex{3}$$

Assume that the variable could represent any real number and then simplify.

1. $$\sqrt { 9 x ^ { 2 } }$$
2. $$\sqrt { 16 y ^ { 2 } }$$
3. $$\sqrt [ 3 ] { 8 y ^ { 3 } }$$
4. $$\sqrt [ 3 ] { 125 a ^ { 3 } }$$
5. $$\sqrt [ 4 ] { 64 x ^ { 4 } }$$
6. $$\sqrt [ 4 ] { 81 y ^ { 4 } }$$
7. $$\sqrt { 36 a ^ { 4 } }$$
8. $$\sqrt { 100 a ^ { 8 } }$$
9. $$\sqrt { 4 a ^ { 6 } }$$
10. $$\sqrt { a ^ { 10 } }$$
11. $$\sqrt { 18 a ^ { 4 } b ^ { 5 } }$$
12. $$\sqrt { 48 a ^ { 5 } b ^ { 3 } }$$
13. $$\sqrt [ 6 ] { 128 x ^ { 6 } y ^ { 8 } }$$
14. $$\sqrt [ 6 ] { a ^ { 6 } b ^ { 7 } c ^ { 8 } }$$
15. $$\sqrt { ( 5 x - 4 ) ^ { 2 } }$$
16. $$\sqrt { ( 3 x - 5 ) ^ { 4 } }$$
17. $$\sqrt { x ^ { 2 } - 6 x + 9 }$$
18. $$\sqrt { x ^ { 2 } - 10 x + 25 }$$
19. $$\sqrt { 4 x ^ { 2 } + 12 x + 9 }$$
20. $$\sqrt { 9 x ^ { 2 } + 6 x + 1 }$$

1. $$3 | x |$$

3. $$2y$$

5. $$2 | x |$$

7. $$6 a ^ { 2 }$$

9. $$2 \left| a ^ { 3 } \right|$$

11. $$3 a ^ { 2 } b ^ { 2 } \sqrt { 2 b }$$

13. $$2 | x y | \sqrt [ 6 ] { 2 y ^ { 2 } }$$

15. $$| 5 x - 4 |$$

17. $$| x - 3 |$$

19. $$| 2x + 3 |$$

Exercise $$\PageIndex{4}$$

Simplify. (Assume all variable expressions represent positive numbers.)

1. $$\sqrt { 49 a ^ { 2 } }$$
2. $$\sqrt { 64 b ^ { 2 } }$$
3. $$\sqrt { x ^ { 2 } y ^ { 2 } }$$
4. $$\sqrt { 25 x ^ { 2 } y ^ { 2 } z ^ { 2 } }$$
5. $$\sqrt { 180 x ^ { 3 } }$$
6. $$\sqrt { 150 y ^ { 3 } }$$
7. $$\sqrt { 49 a ^ { 3 } b ^ { 2 } }$$
8. $$\sqrt { 4 a ^ { 4 } b ^ { 3 } c }$$
9. $$\sqrt { 45 x ^ { 5 } y ^ { 3 } }$$
10. $$\sqrt { 50 x ^ { 6 } y ^ { 4 } }$$
11. $$\sqrt { 64 r ^ { 2 } s ^ { 6 } t ^ { 5 } }$$
12. $$\sqrt { 144 r ^ { 8 } s ^ { 6 } t ^ { 2 } }$$
13. $$\sqrt { ( x + 1 ) ^ { 2 } }$$
14. $$\sqrt { ( 2 x + 3 ) ^ { 2 } }$$
15. $$\sqrt { 4 ( 3 x - 1 ) ^ { 2 } }$$
16. $$\sqrt { 9 ( 2 x + 3 ) ^ { 2 } }$$
17. $$\sqrt { \frac { 9 x ^ { 3 } } { 25 y ^ { 2 } } }$$
18. $$\sqrt { \frac { 4 x ^ { 5 } } { 9 y ^ { 4 } } }$$
19. $$\sqrt { \frac { m ^ { 7 } } { 36 n ^ { 4 } } }$$
20. $$\sqrt { \frac { 147 m ^ { 9 } } { n ^ { 6 } } }$$
21. $$\sqrt { \frac { 2 r ^ { 2 } s ^ { 5 } } { 25 t ^ { 4 } } }$$
22. $$\sqrt { \frac { 36 r ^ { 5 } } { s ^ { 2 } t ^ { 6 } } }$$
23. $$\sqrt [ 3 ] { 27 a ^ { 3 } }$$
24. $$\sqrt [ 3 ] { 125 b ^ { 3 } }$$
25. $$\sqrt [ 3 ] { 250 x ^ { 4 } y ^ { 3 } }$$
26. $$\sqrt [ 3 ] { 162 a ^ { 3 } b ^ { 5 } }$$
27. $$\sqrt [ 3 ] { 64 x ^ { 3 } y ^ { 6 } z ^ { 9 } }$$
28. $$\sqrt [ 3 ] { 216 x ^ { 12 } y ^ { 3 } }$$
29. $$\sqrt [ 3 ] { 8 x ^ { 3 } y ^ { 4 } }$$
30. $$\sqrt [ 3 ] { 27 x ^ { 5 } y ^ { 3 } }$$
31. $$\sqrt [ 3 ] { a ^ { 4 } b ^ { 5 } c ^ { 6 } }$$
32. $$\sqrt [ 3 ] { a ^ { 7 } b ^ { 5 } c ^ { 3 } }$$
33. $$\sqrt [ 3 ] { \frac { 8 x ^ { 4 } } { 27 y ^ { 3 } } }$$
34. $$\sqrt [ 3 ] { \frac { x ^ { 5 } } { 125 y ^ { 6 } } }$$
35. $$\sqrt [ 3 ] { 360 r ^ { 5 } s ^ { 12 } t ^ { 13 } }$$
36. $$\sqrt [ 3 ] { 540 r ^ { 3 } s ^ { 2 } t ^ { 9 } }$$
37. $$\sqrt [ 4 ] { 81 x ^ { 4 } }$$
38. $$\sqrt [ 4 ] { x ^ { 4 } y ^ { 4 } }$$
39. $$\sqrt [ 4 ] { 16 x ^ { 4 } y ^ { 8 } }$$
40. $$\sqrt [ 4 ] { 81 x ^ { 12 } y ^ { 4 } }$$
41. $$\sqrt [ 4 ] { a ^ { 4 } b ^ { 5 } c ^ { 6 } }$$
42. $$\sqrt [ 4 ] { 5 ^ { 4 } a ^ { 6 } c ^ { 8 } }$$
43. $$\sqrt [ 4 ] { 128 x ^ { 6 } }$$
44. $$\sqrt [ 4 ] { 243 y ^ { 7 } }$$
45. $$\sqrt [ 5 ] { \frac { 32 m ^ { 10 } } { n ^ { 5 } } }$$
46. $$\sqrt [ 5 ] { \frac { 3 ^ { 7 } m ^ { 9 } } { n ^ { 10 } } }$$
47. $$- 3 \sqrt { 4 x ^ { 2 } }$$
48. $$7 \sqrt { 9 y ^ { 2 } }$$
49. $$- 5 x \sqrt { 4 x ^ { 2 } y }$$
50. $$- 3 y \sqrt { 16 x ^ { 3 } y ^ { 2 } }$$
51. $$12 a b \sqrt { a ^ { 5 } b ^ { 3 } }$$
52. $$6 a ^ { 2 } b \sqrt { 9 a ^ { 7 } b ^ { 2 } }$$
53. $$2 x \sqrt [ 3 ] { 8 x ^ { 6 } }$$
54. $$- 5 x ^ { 2 } \sqrt [ 3 ] { 27 x ^ { 3 } }$$
55. $$2 a b \sqrt [ 3 ] { - 8 a ^ { 4 } b ^ { 5 } }$$
56. $$5 a ^ { 2 } b \sqrt [ 3 ] { - 27 a ^ { 3 } b ^ { 3 } }$$

1. $$7a$$

3. $$xy$$

5. $$6 x \sqrt { 5 x }$$

7. $$7 a b \sqrt { a }$$

9. $$3 x ^ { 2 } y \sqrt { 5 x y }$$

11. $$8 r s ^ { 3 } t ^ { 2 } \sqrt { t }$$

13. $$x + 1$$

15. $$2 ( 3 x - 1 )$$

17. $$\frac { 3 x \sqrt { x } } { 5 y }$$

19. $$\frac { m ^ { 3 } \sqrt { m } } { 6 n ^ { 2 } }$$

21. $$\frac { r s ^ { 2 } \sqrt { 2 s } } { 5 t ^ { 2 } }$$

23. $$3 a$$

25. $$5 x y \sqrt [ 3 ] { 2 x }$$

27. $$4 x y ^ { 2 } z ^ { 3 }$$

29. $$2 x y \sqrt [ 3 ] { y }$$

31. $$a b c ^ { 2 } \sqrt [ 3 ] { a b ^ { 2 } }$$

33. $$\frac { 2 x \sqrt [ 3 ] { x } } { 3 y }$$

35. $$2 r s ^ { 4 } t ^ { 4 } \sqrt [ 3 ] { 45 r ^ { 2 } t }$$

37. $$3 x$$

39. $$2xy^{2}$$

41. $$a b c \sqrt [ 4 ] { b c ^ { 2 } }$$

43. $$2 x \sqrt [ 4 ] { 8 x ^ { 2 } }$$

45. $$\frac { 2 m ^ { 2 } } { n }$$

47. $$-6x$$

49. $$- 10 x ^ { 2 } \sqrt { y }$$

51. $$12 a ^ { 3 } b ^ { 2 } \sqrt { a b }$$

53. $$4 x ^ { 3 }$$

55. $$- 4 a ^ { 2 } b ^ { 2 } \sqrt [ 3 ] { a b ^ { 2 } }$$

Exercise $$\PageIndex{5}$$

Rewrite the following as a radical expression with coefficient $$1$$.

1. $$3 x \sqrt { 6 x }$$
2. $$5 y \sqrt { 5 y }$$
3. $$a b \sqrt { 10 a }$$
4. $$2 a b ^ { 2 } \sqrt { a }$$
5. $$m ^ { 2 } n \sqrt { m n }$$
6. $$2 m ^ { 2 } n ^ { 3 } \sqrt { 3 n }$$
7. $$2 x \sqrt [ 3 ] { 3 x }$$
8. $$3 y \sqrt [ 3 ] { y ^ { 2 } }$$
9. $$2 y ^ { 2 } \sqrt [ 4 ] { 4 y }$$
10. $$x ^ { 2 } y \sqrt [ 5 ] { 9 x y ^ { 2 } }$$

1. $$\sqrt { 54 x ^ { 3 } }$$

3. $$\sqrt { 10 a ^ { 3 } b ^ { 2 } }$$

5. $$\sqrt { m ^ { 5 } n ^ { 3 } }$$

7. $$\sqrt [ 3 ] { 24 x ^ { 4 } }$$

9. $$\sqrt [ 4 ] { 64 y ^ { 9 } }$$

Exercise $$\PageIndex{6}$$

The period $$T$$ in seconds of a pendulum is given by the formula

$$T = 2 \pi \sqrt { \frac { L } { 32 } }$$

where $$L$$ represents the length in feet of the pendulum. Calculate the period, given each of the following lengths. Give the exact value and the approximate value rounded to the nearest tenth of a second.

1. $$8$$ feet
2. $$32$$ feet
3. $$\frac{1}{2}$$ foot
4. $$\frac{1}{8}$$ foot

1. $$π$$ seconds; $$3.1$$ seconds

3. $$\frac { \pi } { 4 }$$ seconds; $$0.8$$ seconds

Exercise $$\PageIndex{7}$$

The time $$t$$ in seconds an object is in free fall is given by the formula

$$t = \frac { \sqrt { s } } { 4 }$$

where $$s$$ represents the distance in feet the object has fallen. Calculate the time it takes an object to fall, given each of the following distances. Give the exact value and the approximate value rounded to the nearest tenth of a second.

1. $$48$$ feet
2. $$80$$ feet
3. $$192$$ feet
4. $$288$$ feet
5. The speed of a vehicle before the brakes were applied can be estimated by the length of the skid marks left on the road. On dry pavement, the speed $$v$$ in miles per hour can be estimated by the formula $$v = 2 \sqrt { 6 d }$$, where $$d$$ represents the length of the skid marks in feet. Estimate the speed of a vehicle before applying the brakes on dry pavement if the skid marks left behind measure $$27$$ feet. Round to the nearest mile per hour.
6. The radius $$r$$ of a sphere can be calculated using the formula $$r = \frac { \sqrt [ 3 ] { 6 \pi ^ { 2 } V } } { 2 \pi }$$, where $$V$$ represents the sphere’s volume. What is the radius of a sphere if the volume is $$36π$$ cubic centimeters?

1. $$\sqrt{3}$$ seconds; $$1.7$$ seconds

3. $$2\sqrt{3}$$ seconds; $$3.5$$ seconds

5. $$25$$ miles per hour

Exercise $$\PageIndex{8}$$

Given the function find the $$y$$-intercept

1. $$f ( x ) = \sqrt { x + 12 }$$
2. $$f ( x ) = \sqrt { x + 8 } - 3$$
3. $$f ( x ) = \sqrt [ 3 ] { x - 8 }$$
4. $$f ( x ) = \sqrt [ 3 ] { x + 27 }$$
5. $$f ( x ) = \sqrt [ 3 ] { x + 16 }$$
6. $$f ( x ) = \sqrt [ 3 ] { x + 3 } - 1$$

1. $$( 0,2 \sqrt { 3 } )$$

3. $$(0,-2)$$

5. $$( 0,2 \sqrt [ 3 ] { 2 } )$$

Exercise $$\PageIndex{9}$$

Use the distance formula to calculate the distance between the given two points.

1. $$(5,-7)$$ and $$(3,-8)$$
2. $$(-9,7)$$ and $$(-8,4)$$
3. $$(-3,-4)$$ and $$(3,-6)$$
4. $$(-5,-2)$$ and $$(1,-6)$$
5. $$(-1,1)$$ and $$(-4,10)$$
6. $$(8,-3)$$ and $$(2,-12)$$
7. $$(0,-6)$$ and $$(-3,0)$$
8. $$(0,0)$$ and $$(8,-4)$$
9. $$\left( \frac { 1 } { 2 } , - \frac { 1 } { 2 } \right)$$ and $$\left( - 1 , \frac { 3 } { 2 } \right)$$
10. $$\left( - \frac { 1 } { 3 } , 2 \right)$$ and $$\left( \frac { 5 } { 3 } , - \frac { 2 } { 3 } \right)$$

1. $$\sqrt{5}$$ units

3. $$2\sqrt{10}$$ units

5. $$3\sqrt{10}$$ units

7. $$3\sqrt{5}$$ units

9. $$\frac{5}{2}$$ units

Exercise $$\PageIndex{10}$$

Determine whether or not the three points form a right triangle. Use the Pythagorean theorem to justify your answer.

1. $$( 2 , - 1 ) , ( - 1,2 ) , \text { and } ( 6,3 )$$
2. $$( - 5,2 ) , ( - 1 , - 2 ) , \text { and } ( - 2,5 )$$
3. $$( - 5,0 ) , ( 0,3 ) , \text { and } ( 6 , - 1 )$$
4. $$( - 4 , - 1 ) , ( - 2,5 ) , \text { and } ( 7,2 )$$
5. $$( 1 , - 2 ) , ( 2,3 ) , \text { and } ( - 3,4 )$$
6. $$( - 2,1 ) , ( - 1 , - 1 ) , \text { and } ( 1,3 )$$
7. $$( - 4,0 ) , ( - 2 , - 10 ) , \text { and } ( 3 , - 9 )$$
8. $$( 0,0 ) , ( 2,4 ) , \text { and } ( - 2,6 )$$

1. Right triangle

3. Not a right triangle

5. Right triangle

7. Right triangle

Exercise $$\PageIndex{11}$$

1. Give a value for $$x$$ such that $$\sqrt { x ^ { 2 } } \neq x$$. Explain why it is important to assume that the variables represent nonnegative numbers.
2. Research and discuss the accomplishments of Christoph Rudolff. What is he credited for?
3. What is a surd, and where does the word come from?
4. Research ways in which police investigators can determine the speed of a vehicle after an accident has occurred. Share your findings on the discussion board.
15Given two points $$(x_{1} , y_{1} )$$ and $$(x_{2}, y_{2})$$, calculate the distance $$d$$ between them using the formula $$d=\sqrt { \left( x _ { 2 } - x _ { 1 } \right) ^ { 2 } + \left( y _ { 2 } - y _ { 1 } \right) ^ { 2 } }$$.


text:
# Sum of the values of $a$ for which $g^2=f^3-12f^2+45f-a$ has non-constant solutions $f,g\in\mathbb{R}[x]$

Find the sum of the values of the parameter $a$ such that for some non-constant polynomials with real coefficients $f(x)$ and $g(x)$,

$$g(x)^2 =f(x)^3−12 f(x)^2 + 45 f(x) − a$$

My understanding: Since $g(x)^2$ is always positive, $$f(x)^3−12f(x)^2+45f(x)−a \geq0.$$

$f(x)^3−12f(x)^2+45f(x) \geq 0$ for $x \geq 0$ and $<0$ for $x<0$.Therefore, for $x\geq0$, $a \in (-\infty,0]$ and for $x<0$, $a > 0$.

Hence the sum should be zero, since $a$ can take all the possible values. Can anyone please tell me whether the above is correct or not?

-
If $a$ is fixed at the beginning, you can't let it move afterwards. Unless I did not understand the question. – 1015 Mar 6 '13 at 18:30
What values can $a$ take? Real, integer, ...? – vonbrand Mar 6 '13 at 20:49
it can take any value – user65368 Mar 6 '13 at 21:01
This is a problem posed by Brilliant, which provides weekly problems for students to work on. You may view it here - Solve this problem: Poly-polynomials. As the week is over, I'm fine with the posts being kept up. It does explain why there are repeat versions of this problem, and it will unlikely get accepted. - Calvin Lin Brilliant Challenge Master – Calvin Lin Mar 11 '13 at 20:08

Lemma For $\alpha_1, \alpha_2, \ldots, \alpha_n \in \mathbb{C}$ such that $\alpha_1 \ne \alpha_2 \ne \cdots \ne \alpha_n$ and $p(z), q(z)$ any two polynomials over $\mathbb{C}$: $$p(z)^2 = \prod_{i=1}^n(q(z)-\alpha_i) \implies p(z), q(z) \text{ constant }\tag{*}$$

(Proof) Assume the contrary, suppose there are two non-constant polynomials $p(z), q(z)$ such that $$p(z)^2 = \prod_{i=1}^n(q(z)-\alpha_i)$$ Since $\alpha_1, \alpha_2, \ldots, \alpha_n$ are all distinct, the set of roots for $q(z) - \alpha_i, i = 1,\ldots,n$ are disjoint from each other. Since the roots on L.H.S of $(*)$ appear in pairs and $\mathbb{C}[x]$ is an UFD. The roots of each $q(z) - \alpha_i$ also come in pairs. This means we can factor $p(z)$ into $n$ pieces such that:

$$p(z) = \prod_{i=1}^n p_i(z) \;\;\text{ and }\;\; p_i(z)^2 = q(z) - \alpha_i,\, i = 1,\ldots,n$$

Notice for $1 \le i \ne j \le n$, $$(p_i(z) + p_j(z))(p_i(z) - p_j(z)) = (q(z) - \alpha_i) - ( q(z) - \alpha_j ) = \alpha_j - \alpha_i \ne 0$$ are constants. This implies all $p_i(z)$ are constants. As a result, $p(z) = \prod_{i=1}^n p_i(z)$ and $q(z) = p_1(z)^2 + \alpha_1$ are also constants, a contradiction!

(Comment) In the general case when the multiplicity of some $\alpha_i$ is greater than $1$. A similar argument shows that in order for $$p(z)^2 = \prod_{i=1}^n (q(z) - \alpha_i)^{m_i}$$ to have non-constant solutions, a necessary and sufficient condition is at most one of the multiplicity $m_i$ is odd. However, we don't need to use this piece of info for the original problem.

Back to original problem

Applying the lemma to the equation $$g(x)^2 = P(f(x)) = f(x)^3−12 f(x)^2 + 45 f(x) − a\tag{**}$$ In order for it to has non-constant solutions, a necessary condition is the cubic polynomial $P(z) = z^3 - 12z^2 + 45z - a$ has repeated roots. Let $c$ be any repeated root, $(z - c)^2$ will be a factor of $P(z)$ and hence $P'(c) = 3c^2 - 24 c + 45 = 3(c-3)(c-5) = 0 \implies c = 3 \text{ or } 5$.

Case c = 3

$P(3) = 0 \implies a = 54$ and $(**)$ reduces to $g^2 = P(f) = (f-6)(f-3)^2$.

If one assign $6,3,3$ to $\alpha_1,\alpha_2,\alpha_3$ and repeat the arguments in proof of lemma, we see $g(z)$ contains a factor $h(z)$ such that:

$$h(z)^2 = f(z) - 6 \implies g(z)^2 = P(f(z)) = h(z)^2(h(z)^2 + 6 - 3)^2$$

This implies $(**)$ has solutions of the form

\begin{align} f(z) &= h(z)^2 + 6\\ g(z) &= h(z)(h(z)^2 + 3) \end{align}

Case c = 5

$P(5) = 0 \implies a = 50$ and $(**)$ reduces to $g^2 = P(f) = (f-2)(f-5)^2$.

Once again $g(z)$ contains a factor $h(z)$ such that:

$$h(z)^2 = f(z) - 2 \implies g(z)^2 = P(f(z)) = h(z)^2(h(z)^2 + 2 - 5)^2$$

This implies $(**)$ has solutions of the form

\begin{align} f(z) &= h(z)^2 + 2\\ g(z) &= h(z)(h(z)^2 - 3) \end{align}

And the desired answer is $54 + 50 = 104$.

-
And there's still no upvote...+1. – 1015 Mar 7 '13 at 20:57

This makes no sense: there's no reason that the sign of $f(x)^3 - 12 f(x)^2 + 45 f(x)$ should have anything to do with the sign of $x$.

In any case, you want $f(x)^3 - 12 f(x)^2 + 45 f(x) - a \ge 0$ for all $x$. That can only happen if $f$ is a polynomial of even degree.

As a matter of fact, if you want $f$ to be a quadratic polynomial (and thus $g$ cubic), you need $a = 50$ or $54$:

$$\left( {x}^{2}+2 \right) ^{3}-12\, \left( {x}^{2}+2 \right) ^{2}+45\, \left({x}^{2}+2\right) - 50= \left( {x}^{3}-3\,x \right) ^{2}$$

$$\left( {x}^{2}+6 \right) ^{3}-12\, \left( {x}^{2}+6 \right) ^{2}+45\, \left({x}^{2}+6 \right) - 54= \left( {x}^{3}+3\,x \right) ^{2}$$

I don't know if there are solutions of higher degree.

EDIT: Let $P(z) = z^3 - 12 z^2 + 45 z - a$. Suppose $P(f(x)) = g(x)^2$, where $f$ and $g$ are nonconstant polynomials. If $g$ has degree $d$, then $f$ has degree $2d/3 < d$.

Differentiating the equation $P(f(x)) = g(x)^2$, we get $P'(f(x)) f'(x) = 2 g(x) g'(x)$. In particular, if $r$ is a (real or complex) root of $g(x)$, then either $P'(f(r)) = 0$ or $f'(r) = 0$. If $P'(f(r)) = 0$, then since the roots of $P'(z) = 3 z^2 - 24 z + 45 = 3 (z-3)(z-5)$ are $3$ and $5$, we have $f(r) = 3$ or $f(r) = 5$. Thus $P(3) = 0$ or $P(5) = 0$. But $P(3) = 54 - a$ and $P(5) = 50 - a$, so $a = 50$ or $54$.

Now it is possible that $f'(r) = 0$ for all roots $r$ of $g(x)$. But $f'$ has degree $< d - 1$, so there is at least one root $r$ which has higher multiplicity as a root of $g$ than it does as a root for $f'$. That is, for some $r$, $c \ne 0$ and positive integer $k$ we have $f(x) = f(r) + c (x-r)^{k} + O((x-r)^{k+1})$ while $g(x) = O((x-r)^{k})$. Then $$P(f(x)) = P'(f(r)) c (x-r)^k + O((x-r)^{k+1}) = g(x)^2 = O((x-r)^{k+1})$$ so again $P'(f(r)) = 0$.

-
In fact, when $a=50, 54$, there are solutions of higher degree, but there are no solutions for all other $a$. I'll be posting an answer regarding this when I get home in a while. – Ivan Loh Mar 7 '13 at 8:01

It is easy to plot $P(x)=x^3-12x^2+45x$. (This can also be done manually, by looking at critical points) Looking at the behaviour of $P(x)$, we note that the cubic equation $P(x)=a$ has 1 real root and 2 distinct complex roots (conjugate pair) for $a<50, a>54$, 3 distinct real roots for $50<a<54$, and 2 real roots (with 1 repeated) for $a=50, 54$.

Consider $a \not =50, 54$. Then the cubic equation $P(x)=a$ has at least 1 real root $c$ and no repeated complex roots. Factorise $g(x)^2=P(f(x))-a=(f(x)-c)(f(x)^2+pf(x)+q)$, where $p, q \in \mathbb{R}$.

We show that $(f(x)-c)$ and $(f(x)^2+pf(x)+q)$ have no common complex root. Assume on the contrary that they have a common root $\alpha$, then $f(\alpha)$ is a common complex root of $x-c$ and $x^2+px+q$, so $f(\alpha)$ is a repeated complex root of $P(x)=a$, a contradiction.

Now each complex root in $g(x)^2$ has even multiplicity, so each complex root in $(f(x)^2+pf(x)+q)$ has even multiplicity. Since $(f(x)^2+pf(x)+q) \in \mathbb{R}[x]$ and $(f(x)^2+pf(x)+q)$ has positive leading coefficient, this implies that $(f(x)^2+pf(x)+q)=h(x)^2$ for some $h(x) \in \mathbb{R}[x]$. (To see why, note that the complex roots come in conjugate pairs, so that $(f(x)^2+pf(x)+q)$ is the product of squares of quadratics.)

Finally, observe that since $x^2+px+q$ has no repeated roots, we have $x^2+px+q=(x+\frac{p}{2})^2+r$, where $r \not =0, r \in \mathbb{R}$. Thus $h(x)^2=(f(x)^2+pf(x)+q)=(f(x)+\frac{p}{2})^2+r$, so $r=(h(x)-(f(x)+\frac{p}{2}))(h(x)+(f(x)+\frac{p}{2}))$, so both $(h(x)-(f(x)+\frac{p}{2}))$ and $(h(x)+(f(x)+\frac{p}{2}))$ are constant, so that $f(x)$ must be constant, a contradiction.

For $a=50$, factorise $g(x)^2=P(f(x))-50=(f(x)-2)(f(x)-5)^2$, so we have the general family of solutions $f(x)=q(x)^2+2, g(x)=q(x)(f(x)-5)$, where we restrict $q(x)$ to be nonconstant, since both $f(x), g(x)$ are nonconstant.

For $a=54$, factorise $g(x)^2=P(f(x))-54=(f(x)-6)(f(x)-3)^2$, so we have the general family of solutions $f(x)=q(x)^2+6, g(x)=q(x)(f(x)-3)$, where we restrict $q(x)$ to be nonconstant, since both $f(x), g(x)$ are nonconstant.

Edit: Forgot to answer the question. To conclude, the sum of values of permissible $a$ is $50+54=104$.

-


text:
### A trigonometric identity is given by cos2(x/2)=(tanx+sinx)/2.tanx verify that the identity is correct by calculating each side of the equation substituting x=pi/5

Problem :
A trigonometric identity is given by cos2(x/2)=(tanx+sinx)/2.tanx verify that the identity is correct by calculating each side of the equation substituting x=pi/5

>> %A trigonometric identity is given by cos2(x/2)=(tanx+sinx)/2.tanx verify that the identity is correct by calculating each side of the equation substituting x=pi/5%
>> x=pi/5;
>> LHS=cos(x/2)^2

LHS =

0.9045

>> RHS=(tan(x)+sin(x))/(2*tan(x))

RHS =

0.9045


text:
当前位置:

# 数学学科离散数学研究所学术报告（董峰明 南洋理工大学）

 报告题目：  New expressions for order polynomials and chromatic polynomials报 告  人：董峰明，新加坡南洋理工大学副教授（终身职位）, 博导报告时间：2019年12月18日14:00点报告地点：20幢404室摘要： In 1970, Stanley introduced the order polynomial and the strict order polynomial of a poset (i.e. partially ordered set). Let $P$ be a poset on $n$ elements with a binary relation $\preceq$. For $u,v \in P$, let $u \prec v$ mean that $u \preceq v$ but $u \neq v$. A mapping $\sigma :P \rightarrow[m]$ is said to be {\it order-preserving}  (resp., {\it strictly order-preserving}) if $u \preceq v$ implies that  $\sigma(u) \leq \sigma(v)$ (resp., $u \prec v$  implies that $\sigma(u) < \sigma(v)$). Let $\Omega(P, x)$ (resp., $\bar{\Omega}(P, x)$)  be the function which counts the number of order-preserving (resp., strictly order-preserving) mappings $\sigma :P \rightarrow[m]$ whenever $x = m$ is a positive integer. Both $\Omega(P, x)$ and $\bar{\Omega}(P, x)$ are polynomials in $x$ of degree $n$ and are respectively called the {\it order polynomial} and the {\it strict order polynomial} of $P$. In this talk, I will introduce the order polynomial $\Omega(P, x)$ and its computations. I will also present our latest result on a new expression for $\Omega(P, x)$. By applying this new result and Stanley's work on the relation between order polynomials and chromatic polynomials $\chi(G, x)$ of graphs $G$, a new expression for $\chi(G, x)$ follows directly.  个人概况：董峰明，南洋理工大学副教授（终身职位）, 博导。 主要从事图论与组合数学方面的研究，解决了包括牛津大学 Dominic Welsh 教授提出的 the Shameful Conjecture在内的若干公开问题。在Journal of Combinatorial Theory, Series A，Journal of Combinatorial Theory, Series B，Journal of Graph Theory，European Journal of Combinatorics, SIAM Journal on Discrete Mathematics, Electronic Journal of Combinatorics等杂志上发表学术论文70余篇。 邀请人：严慧芳


text:
# indefinite integral

• Aug 6th 2010, 08:55 PM
john-1
indefinite integral
Find the indefinite integral of e^(f(x)+ln(f'(x))) dx

I do have the steps from my teacher, but I'm confused about how to get to the first step which is simplifying to e^ f(x) f'(x)
Would anyone mind explaining how to get to this first step as I do understand the rest except this?

• Aug 6th 2010, 09:11 PM
sa-ri-ga-ma
$e^{(f(x) + ln(f'(x))} = e^{f(x)}e^{ln(f'(x)} = e^{f(x)}f'(x)$

because e^ln(a) = a.


text:
# 2017 Vision Examples

## LabVIEW

The 2017 LabVIEW Vision Example is included with the other LabVIEW examples. From the Splash screen, click Support->Find FRC® Examples or from any other LabVIEW window, click Help->Find Examples and locate the Vision folder to find the 2017 Vision Example. The example images are bundled with the example.

## C++/Java

We have provided a GRIP project and the description below, as well as the example images, bundled into a ZIP that can be found on TeamForge.

See Using Generated Code in a Robot Program for details about integrating GRIP generated code in your robot program.

The code generated by the included GRIP project will find OpenCV contours for green particles in images like the ones included in the Vision Images folder of this ZIP. From there you may wish to further process these contours to assess if they are the target. To do this:

1. Use the boundingRect method to draw bounding rectangles around the contours

2. The LabVIEW example code calculates 5 separate ratios for the target. Each of these ratios should nominally equal 1.0. To do this, it sorts the contours by size, then starting with the largest, calculates these values for every possible pair of contours that may be the target, and stops if it finds a target or returns the best pair it found.

In the formulas below, each letter refers to a coordinate of the bounding rect (H = Height, L = Left, T = Top, B = Bottom, W = Width) and the numeric subscript refers to the contour number (1 is the largest contour, 2 is the second largest, etc).

• Top height should be 40% of total height (4 in / 10 in):

$\textit{Group Height} = \frac{H_1}{0.4 (B_2 - T_1)}$
• Top of bottom stripe to top of top stripe should be 60% of total height (6 in / 10 in):

$\textit{dTop} = \frac{T_2 - T_1}{0.6 (B_2 - T_1)}$
• The distance between the left edge of contour 1 and the left edge of contour 2 should be small relative to the width of the 1st contour; then we add 1 to make the ratio centered on 1:

$\textit{LEdge} = \frac{L_1 - L_2}{W_1} + 1$
• The widths of both contours should be about the same:

$\textit{Width ratio} = \frac{W_1}{W_2}$
• The larger stripe should be twice as tall as the smaller one

$\textit{Height ratio} = \frac{H_1}{2 H_2}$

Each of these ratios is then turned into a 0-100 score by calculating:

$100 - (100 \cdot \mathrm{abs}(1 - \textit{Val}))$
1. To determine distance, measure pixels from top of top bounding box to bottom of bottom bounding box:

$\textit{distance} = \frac{\textit{Target height in ft.} (10/12) \cdot \textit{YRes}}{2 \cdot \textit{PixelHeight} \cdot \tan (\textit{viewAngle of camera})}$

The LabVIEW example uses height as the edges of the round target are the most prone to noise in detection (as the angle points further from the camera the color looks less green). The downside of this is that the pixel height of the target in the image is affected by perspective distortion from the angle of the camera. Possible fixes include:


text:
# For developers: AST Nodes and Transformations¶

## AST Nodes¶

class Node(parent=None)

Base class for all AST nodes.

property args

Returns all arguments/children of this node.

Return type
property symbols_defined

Set of symbols which are defined by this node.

Return type
property undefined_symbols

Symbols which are used but are not defined inside this node.

Return type
subs(subs_dict)

Inplace! Substitute, similar to sympy’s but modifies the AST inplace.

Return type

None

atoms(arg_type)

Returns a set of all descendants recursively, which are an instance of the given type.

Return type
class Conditional(condition_expr, true_block, false_block=None)

Conditional that maps to a ‘if’ statement in C/C++.

Try to avoid using this node inside of loops, since currently this construction can not be vectorized. Consider using assignments with sympy.Piecewise in this case.

Parameters
subs(subs_dict)

Inplace! Substitute, similar to sympy’s but modifies the AST inplace.

property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

replace_by_true_block()

Replaces the conditional by its True block

replace_by_false_block()

Replaces the conditional by its False block

class KernelFunction(body, target, backend, compile_function, ghost_layers, function_name='kernel')
class Parameter(symbol, fields)

Function parameter.

Each undefined symbol in a KernelFunction node becomes a parameter to the function. Parameters are either symbols introduced by the user that never occur on the left hand side of an Assignment, or are related to fields/arrays passed to the function.

A parameter consists of the typed symbol (symbol property). For field related parameters this is a symbol defined in pystencils.kernelparameters. If the parameter is related to one or multiple fields, these fields are referenced in the fields property.

property target

Currently either ‘cpu’ or ‘gpu’

property backend

Backend for generating the code e.g. ‘llvm’, ‘c’, ‘cuda’

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

property args

Returns all arguments/children of this node.

property fields_accessed

fields which are accessed inside this kernel function

Type

Set of Field instances

Return type
get_parameters()

Returns list of parameters for this function.

This function is expensive, cache the result where possible!

Return type
class SkipIteration(parent=None)
property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class Block(nodes)
property args

Returns all arguments/children of this node.

subs(subs_dict)

Inplace! Substitute, similar to sympy’s but modifies the AST inplace.

Return type

None

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class PragmaBlock(pragma_line, nodes)
class LoopOverCoordinate(body, coordinate_to_loop_over, start, stop, step=1, is_block_loop=False)
subs(subs_dict)

Inplace! Substitute, similar to sympy’s but modifies the AST inplace.

property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class SympyAssignment(lhs_symbol, rhs_expr, is_const=True, use_auto=False)
subs(subs_dict)

Inplace! Substitute, similar to sympy’s but modifies the AST inplace.

property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class ResolvedFieldAccess
class TemporaryMemoryAllocation(typed_symbol, size, align_offset)

Node for temporary memory buffer allocation.

Always allocates aligned memory.

Parameters
• typed_symbol (TypedSymbol) – symbol used as pointer (has to be typed)

• size – number of elements to allocate

• align_offset – the align_offset’s element is aligned

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

property args

Returns all arguments/children of this node.

offset(byte_alignment)

Number of ELEMENTS to skip for a pointer that is aligned to byte_alignment.

class TemporaryMemoryFree(alloc_node)
property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

property args

Returns all arguments/children of this node.

class SourceCodeComment(text)
property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class EmptyLine
property args

Returns all arguments/children of this node.

property symbols_defined

Set of symbols which are defined by this node.

property undefined_symbols

Symbols which are used but are not defined inside this node.

class ConditionalFieldAccess

pystencils.Field.Access that is only executed if a certain condition is met. Can be used, for instance, for out-of-bound checks.

## Transformations¶

class NestedScopes

Symbol visibility model using nested scopes

• every accessed symbol that was not defined before, is added as a “free parameter”

• free parameters are global, i.e. they are not in scopes

• push/pop adds or removes a scope

>>> s = NestedScopes()
>>> s.access_symbol("a")
>>> s.is_defined("a")
False
>>> s.free_parameters
{'a'}
>>> s.define_symbol("b")
>>> s.is_defined("b")
True
>>> s.push()
>>> s.is_defined_locally("b")
False
>>> s.define_symbol("c")
>>> s.pop()
>>> s.is_defined("c")
False

unify_shape_symbols(body, common_shape, fields)

Replaces symbols for array sizes to ensure they are represented by the same unique symbol.

When creating a kernel with variable array sizes, all passed arrays must have the same size. This is ensured when the kernel is called. Inside the kernel this means that only on symbol has to be used instead of one for each field. For example shape_arr1[0] and shape_arr2[0] must be equal, so they should also be represented by the same symbol.

Parameters
• body – ast node, for the kernel part where substitutions is made, is modified in-place

• common_shape – shape of the field that was chosen

• fields – all fields whose shapes should be replaced by common_shape

get_common_shape(field_set)

Takes a set of pystencils Fields and returns their common spatial shape if it exists. Otherwise ValueError is raised

make_loop_over_domain(body, iteration_slice=None, ghost_layers=None, loop_order=None)

Uses pystencils.field.Field.Access to create (multiple) loops around given AST.

Parameters
• body – Block object with inner loop contents

• iteration_slice – if not None, iteration is done only over this slice of the field

• ghost_layers – a sequence of pairs for each coordinate with lower and upper nr of ghost layers if None, the number of ghost layers is determined automatically and assumed to be equal for a all dimensions

• loop_order – loop ordering from outer to inner loop (optimal ordering is same as layout)

Returns

tuple of loop-node, ghost_layer_info

create_intermediate_base_pointer(field_access, coordinates, previous_ptr)

Addressing elements in structured arrays is done with $$ptr\left[ \sum_i c_i \cdot s_i \right]$$ where $$c_i$$ is the coordinate value and $$s_i$$ the stride of a coordinate. The sum can be split up into multiple parts, such that parts of it can be pulled before loops. This function creates such an access for coordinates $$i \in \mbox{coordinates}$$. Returns a new typed symbol, where the name encodes which coordinates have been resolved.

Parameters
• field_access – instance of pystencils.field.Field.Access which provides strides and offsets

• coordinates – mapping of coordinate ids to its value, where stride*value is calculated

• previous_ptr – the pointer which is de-referenced

Returns

tuple with the new pointer symbol and the calculated offset

Examples

>>> field = Field.create_generic('myfield', spatial_dimensions=2, index_dimensions=1)
>>> x, y = sp.symbols("x y")
>>> prev_pointer = TypedSymbol("ptr", "double")
>>> create_intermediate_base_pointer(field[1,-2](5), {0: x}, prev_pointer)
(ptr_01, _stride_myfield_0*x + _stride_myfield_0)
>>> create_intermediate_base_pointer(field[1,-2](5), {0: x, 1 : y }, prev_pointer)
(ptr_01_1m2, _stride_myfield_0*x + _stride_myfield_0 + _stride_myfield_1*y - 2*_stride_myfield_1)

parse_base_pointer_info(base_pointer_specification, loop_order, spatial_dimensions, index_dimensions)

Creates base pointer specification for resolve_field_accesses() function.

Specification of how many and which intermediate pointers are created for a field access. For example [ (0), (2,3,)] creates on base pointer for coordinates 2 and 3 and writes the offset for coordinate zero directly in the field access. These specifications are defined dependent on the loop ordering. This function translates more readable version into the specification above.

Allowed specifications:
• “spatialInner<int>” spatialInner0 is the innermost loop coordinate, spatialInner1 the loop enclosing the innermost

• “spatialOuter<int>” spatialOuter0 is the outermost loop

• “index<int>”: index coordinate

• “<int>”: specifying directly the coordinate

Parameters
• base_pointer_specification – nested list with above specifications

• loop_order – list with ordering of loops from outer to inner

• spatial_dimensions – number of spatial dimensions

• index_dimensions – number of index dimensions

Returns

list of tuples that can be passed to resolve_field_accesses()

Examples

>>> parse_base_pointer_info([['spatialOuter0'], ['index0']], loop_order=[2,1,0],
...                         spatial_dimensions=3, index_dimensions=1)
[[0], [3], [1, 2]]

get_base_buffer_index(ast_node, loop_counters=None, loop_iterations=None)

Used for buffer fields to determine the linearized index of the buffer dependent on loop counter symbols.

Parameters
• ast_node – ast before any field accesses are resolved

• loop_counters – for CPU kernels: leave to default ‘None’ (can be determined from loop nodes) for GPU kernels: list of ‘loop counters’ from inner to outer loop

• loop_iterations – number of iterations of each loop from inner to outer, for CPU kernels leave to default

Returns

base buffer index - required by ‘resolve_buffer_accesses’ function

resolve_field_accesses(ast_node, read_only_field_names={}, field_to_base_pointer_info=mappingproxy({}), field_to_fixed_coordinates=mappingproxy({}))

Substitutes pystencils.field.Field.Access nodes by array indexing

Parameters
• ast_node – the AST root

• field_to_base_pointer_info – a list of tuples indicating which intermediate base pointers should be created for details see parse_base_pointer_info()

• field_to_fixed_coordinates – map of field name to a tuple of coordinate symbols. Instead of using the loop counters to index the field these symbols are used as coordinates

Returns

transformed AST

move_constants_before_loop(ast_node)

Moves pystencils.ast.SympyAssignment nodes out of loop body if they are iteration independent.

Call this after creating the loop structure with make_loop_over_domain()

split_inner_loop(ast_node, symbol_groups)

Splits inner loop into multiple loops to minimize the amount of simultaneous load/store streams

Parameters
• ast_node (Node) – AST root

• symbol_groups – sequence of symbol sequences: for each symbol sequence a new inner loop is created which updates these symbols and their dependent symbols. Symbols which are in none of the symbolGroups and which no symbol in a symbol group depends on, are not updated!

cut_loop(loop_node, cutting_points)

Cuts loop at given cutting points.

One loop is transformed into len(cuttingPoints)+1 new loops that range from old_begin to cutting_points[1], …, cutting_points[-1] to old_end

Modifies the ast in place

Returns

list of new loop nodes

simplify_conditionals(node, loop_counter_simplification=False)

Removes conditionals that are always true/false.

Parameters
• node (Node) – ast node, all descendants of this node are simplified

• loop_counter_simplification (bool) – if enabled, tries to detect if a conditional is always true/false depending on the surrounding loop. For example if the surrounding loop goes from x=0 to 10 and the condition is x < 0, it is removed. This analysis needs the integer set library (ISL) islpy, so it is not done by default.

Return type

None

cleanup_blocks(node)

Curly Brace Removal: Removes empty blocks, and replaces blocks with a single child by its child

Return type

None

class KernelConstraintsCheck(type_for_symbol, check_independence_condition, check_double_write_condition=True)

Checks if the input to create_kernel is valid.

Test the following conditions:

• SSA Form for pure symbols:
• Every pure symbol may occur only once as left-hand-side of an assignment

• Every pure symbol that is read, may not be written to later

• Independence / Parallelization condition:
• a field that is written may only be read at exact the same spatial position

(Pure symbols are symbols that are not Field.Accesses)

class FieldAndIndex(field, index)
property field

Alias for field number 0

property index

Alias for field number 1

add_types(eqs, type_for_symbol, check_independence_condition)

Traverses AST and replaces every sympy.Symbol by a pystencils.typedsymbol.TypedSymbol.

Parameters
• eqs – list of equations

• type_for_symbol – dict mapping symbol names to types. Types are strings of C types like ‘int’ or ‘double’

• check_independence_condition – check that loop iterations are independent - this has to be skipped for indexed kernels

Returns

fields_read, fields_written, typed_equations set of read fields, set of written fields,

list of equations where symbols have been replaced by typed symbols

insert_casts(node)

Checks the types and inserts casts and pointer arithmetic where necessary.

Parameters

node – the head node of the ast

Returns

modified AST

remove_conditionals_in_staggered_kernel(function_node, include_first=True)

Removes conditionals of a kernel that iterates over staggered positions by splitting the loops at last or first and last element

Return type

None

typing_from_sympy_inspection(eqs, default_type='double', default_int_type='int64')

Creates a default symbol name to type mapping. If a sympy Boolean is assigned to a symbol it is assumed to be ‘bool’ otherwise the default type, usually (‘double’)

Parameters
• eqs – list of equations

• default_type – the type for non-boolean symbols

Returns

dictionary, mapping symbol name to type

get_next_parent_of_type(node, parent_type)

Returns the next parent node of given type or None, if root is reached.

Traverses the AST nodes parents until a parent of given type was found. If no such parent is found, None is returned

parents_of_type(node, parent_type, include_current=False)

Generator for all parent nodes of given type

get_optimal_loop_ordering(fields)

Determines the optimal loop order for a given set of fields. If the fields have different memory layout or different sizes an exception is thrown.

Parameters

fields – sequence of fields

Returns

list of coordinate ids, where the first list entry should be the outermost loop

get_loop_hierarchy(ast_node)

Determines the loop structure around a given AST node, i.e. the node has to be inside the loops.

Returns

sequence of LoopOverCoordinate nodes, starting from outer loop to innermost loop

get_loop_counter_symbol_hierarchy(astNode)

Determines the loop counter symbols around a given AST node. :param astNode: the AST node :return: list of loop counter symbols, where the first list entry is the symbol of the innermost loop

replace_inner_stride_with_one(ast_node)

Replaces the stride of the innermost loop of a variable sized kernel with 1 (assumes optimal loop ordering).

Variable sized kernels can handle arbitrary field sizes and field shapes. However, the kernel is most efficient if the innermost loop accesses the fields with stride 1. The inner loop can also only be vectorized if the inner stride is 1. This transformation hard codes this inner stride to one to enable e.g. vectorization.

Warning: the assumption is not checked at runtime!

Return type

None

loop_blocking(ast_node, block_size)

Blocking of loops to enhance cache locality. Modifies the ast node in-place.

Parameters
• ast_node (KernelFunction) – kernel function node before vectorization transformation has been applied

• block_size – sequence defining block size in x, y, (z) direction

Return type

int

Returns

number of dimensions blocked