text:
# NCERT Class 9 Solutions: Number Systems (Chapter 1) Exercise 1.5 – Part 1

• Previous

Q-1 Classify the following numbers as rational or irrational:

Solution:

• Given multiple numbers and classify the numbers as rational or irrational

1. Since it is non-terminating and non-recurring number

So, it is an irrational number

2. Since the number can be written form

So, it is a rational number

3. Since the number can be written form

So, it is a rational number

4. Since it is non-terminating and non-recurring number

So, it is an irrational number

5. Since it is non-terminating and non-recurring number

So, it is an irrational number

Q-2 Simplify each of the following expressions:

Solution:

1. =

2. Using identify

3. Using identify

4. Using identify


text:
AriCalculator is a home made pocket calculator.
10-30-2018, 06:43 AM
Post: #81
 grsbanks Senior Member Posts: 730 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
I've read a document somewhere that explains how CORDIC can be used to do pretty much everything except hang the washing out. Regardless, I used straightforward long multiplication and long division and a nifty algorithm that gets you a digit of precision for each iteration to calculate sqrt(x).

CORDIC got me sin/cos and I just divide one by the other to get tan. I have a good algorithm that uses 1+10^(-i) constants for exp(x) and ln(x) but have found a way to get sinh/cosh & co. using CORDIC so will no doubt use that.

Results are encouraging. I'm using a DM42 to calculate the constants I need and to check my results. I'd be stuffed if I didn't have that starting point

For now I'm just using the standard gcc toolchain in 64-bit Linux and producing a static library that I'm linking to a test program to obtain/test results. When the time comes to start testing on LPC1115 hardware, I'll be using the ARM-embedded toolchain. It's the same one as for the DM42.
10-31-2018, 07:53 AM
Post: #82
 Dan Member Posts: 126 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
That's great, sounds like a really cool project. I use the microcontroller's timer to compare algorithms, so if you ever document the ones you are using I would be interested in trying them out.
10-31-2018, 08:06 AM (This post was last modified: 10-31-2018 09:45 AM by grsbanks.)
Post: #83
 grsbanks Senior Member Posts: 730 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
The library will be fully open source once I'm satisfied that it's working properly. I'm writing it in C that's as portable as I can make it so it should work on pretty much any 32- or 64-bit system.

As far as usage is concerned, this small test program in C is linked to the library:

Code:
#include <stdlib.h> #include <stdio.h> #include "decfp.h" void prt(_NUM*); int main(int argc, char** argv) {          _NUM x, sn, cs, tn;     RealToNum(&CONST_PI_2,&x);     prt(&x);     NumSinCos(&x,&sn,&cs);     NumScaleTrigVector(&sn,&cs);     prt(&sn);     prt(&cs);          Setting_ErrorOnOverflow = TRUE;     /* NumTan does this anyway */     DECFP_ERR res = NumDivide(&sn,&cs,&tn);     if (res)         printf("ERROR: %s\n",ErrorMessage(res));     else         prt(&tn);          Setting_ErrorOnOverflow = FALSE;     res = NumDivide(&sn,&cs,&tn);     if (res)         printf("ERROR: %s\n",ErrorMessage(res));     else         prt(&tn);     NumNegate(&x,&x);          NumSinCos(&x,&sn,&cs);     NumScaleTrigVector(&sn,&cs);     prt(&sn);     prt(&cs);          Setting_ErrorOnOverflow = TRUE;     res = NumDivide(&sn,&cs,&tn);     if (res)         printf("ERROR: %s\n",ErrorMessage(res));     else         prt(&tn);          Setting_ErrorOnOverflow = FALSE;     res = NumDivide(&sn,&cs,&tn);     if (res)         printf("ERROR: %s\n",ErrorMessage(res));     else         prt(&tn);          return 0; } void prt(_NUM* x) {     char* bfr = NumOutFullPrecision(x);     printf("%s\n",bfr);     free(bfr); }

Gives this output:

Code:
\$ bin/decfp +1.57079632679489661923132e+0000 +1.00000000000000000000000e+0000 +0.00000000000000000000000e+0000 ERROR: Divide by zero +9.99999999999999999999999e+9999 -1.00000000000000000000000e+0000 +0.00000000000000000000000e+0000 ERROR: Divide by zero -9.99999999999999999999999e+9999
11-01-2018, 04:11 AM
Post: #84
 Dan Member Posts: 126 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
(10-31-2018 08:06 AM)grsbanks Wrote:  The library will be fully open source once I'm satisfied that it's working properly.

Way to go, same here.
02-20-2019, 06:39 AM
Post: #85
 Dan Member Posts: 126 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
I have finished porting the firmware to the S12XEP100. I made several changes to the keypad, including adding an extra row of 6 buttons:

03-13-2019, 05:58 AM (This post was last modified: 03-13-2019 06:18 AM by Dan.)
Post: #86
 Dan Member Posts: 126 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
And here it is, two years in the making, the absolute assembly file for a scientific, keystroke programmable RPN calculator (click on "View Raw").

I've started rewriting the code in C++ for the TI Tiva-C LaunchPad, which features a 32-bit ARM Cortex-M4F CPU.

It can be programmed using TI's free Code Composer Studio, which is available for Windows, Mac OS and Linux.

03-13-2019, 08:30 PM
Post: #87
 KeithB Member Posts: 156 Joined: Jan 2017
RE: AriCalculator is a home made pocket calculator.
If you have a Mac, do not be in too much of a rush to get CCS. Version 9, which will be fully 64-bit on the Mac, will be out in a few weeks to a month.

Commercial:
CCS and the TI launchpads are a great way to get into Arduino-like embedded hobbying. The SimpleLink boards incorporate a radio transceiver and an MCU for low cost wireless applications.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)

format: plain


text:
# : Write your observations while doing an activity of burning of magnesium ribbon?

Verified
197.1k+ views
Hint:When we burn magnesium ribbon, chemical reaction takes place. The process in which reactants are converted to one or more different substances that are the products is called chemical reaction. It converts into its oxide with high amounts of heat released.

$2Mg + {O_2} \to 2MgO$
where $Mg$ is magnesium, ${O_2}$ is oxygen and $MgO$ is magnesium oxide.
Magnesium ribbon when burnt in presence of oxygen forms magnesium oxide. This reaction takes place with the help of Bunsen burner. In this reaction, the changes are observed without change in composition of substances. The changes which are observed are changes in colour, hardness etc. Magnesium oxide obtained is white in colour. Here the oxidation state of magnesium deviates from 0 to $+ 2$. The oxidation state of oxygen deviates from 0 to $- 2$. Hence in this reaction, magnesium undergoes oxidation and oxygen undergoes reduction. Due to this, the above reaction is a redox reaction. Also, heat is released in the above reaction. This makes the reaction an exothermic reaction.


text:
# Time difference evaluation in a Michelson-Morley apparatus with arbitrary orientation

Historically, by assuming the validity of the Lorentz-Fitzgerald contraction, the null result obtained in the Michelson-Morley experiment can be explained. In particular light travels along the two arms of the apparatus (one positioned parallel to the direction of motion and one perpendicular) with a time difference given by: $$t_1-t_2= \frac{2(l_{10}-l_{20})/c}{(1-v^2/c^2)^{1 \over 2}}$$ Where $$l_{10}$$ and $$l_{20}$$ are the normal length of each arm i.e for the arms at rest. This relation is true also if we rotate the interferometer by 90° assuming the contraction. I want to prove that the relation holds for every angle of rotation. Assuming the contraction I reckon that the angle formed by an arm and the direction of $$\vec{v}$$ (the speed of the apparatus), measured with the system in motion and at rest would be different so we have the relations for each arm: $$(l_{10})^2=(l_1 \sin \theta)^2+\frac{(l_1 \cos \theta)^2}{1-v^2/c^2}$$ $$(l_{20})^2=(l_2 \cos \theta)^2 +\frac{(l_2 \sin \theta)^2}{1-v^2/c^2}$$ The first relation has been given by my textbook whereas the second has been derived accordingly by my self. I suppose that $$\theta$$ is the angle between the first arm and $$\vec{v}$$ with the system in motion. Using this relations I'm not able to obtain the time difference stated before. I think that light must travel with a certain angle different from $$\theta$$ in order for the ray to reach the mirror of the interferometer and bounce back compensating the motion of the system. For example, in the case of the first arm, taking the apparatus as our system of reference i think the speed will be, according to Galilean transformation: $$(v_c)^2=(c \cos \phi -v)^2+(c \sin \theta)^2$$ for the ray traveling towards the mirror and for the one that bounced back: $$(v_c)^2=(c \cos \phi +v)^2+(c \sin \theta)^2$$ Any hint or help in the solution process would be appreciated. Thank you in advance.


text:
# Undefined behavior when formatting vertically aligned multicolumn commands with different column spans #143

Closed
opened this issue Oct 16, 2018 · 11 comments
Closed

# Undefined behavior when formatting vertically aligned multicolumn commands with different column spans#143

opened this issue Oct 16, 2018 · 11 comments
Labels

### douglasrizzo commented Oct 16, 2018 • edited

 Hi there. I'd like some clarification regarding the behavior of the multiColumnGrouping: 1 option with a particular example I have. I have the following tabular environment, whose columns I have aligned by hand in a way that looks sensible to me: \begin{tabular}{cc|c||c|c} \multicolumn{3}{c||}{\textbf{Exploração Fácil}} & \multicolumn{2}{c}{\textbf{Exploração Difícil}} \\ \multicolumn{2}{c|}{\emph{Ótimo humano}} & \emph{Abuso da pontuação} & \emph{Recompensas densas} & \emph{Recompensas esparsas} \\ \hline Assault & Asterix & Beam Rider & Alien & Freeway \\ Asteroids & Atlantis & Kangaroo & Amidar & Gravitar \\ Battle Zone & Berzerk & Krull & Bank Heist & Montezuma's Revenge \\ Bowling & Boxing & Kung Fu Master & Frostbite & Pitfall \\ Breakout & Centipede & Road Runner & H E R O & Private Eye \\ Chopper Cmd & Crazy Climber & Seaquest & Ms Pac Man & Solaris \\ Defender & Demon Attack & Up N Down & Q Bert & Venture \\ \hline \end{tabular}  However, when I use latexindent in this file, it aligns my columns like so: \begin{tabular}{cc|c||c|c} \multicolumn{3}{c||}{\textbf{Exploração Fácil}} & \multicolumn{2}{c}{\textbf{Exploração Difícil}} \\ \multicolumn{2}{c|}{\emph{Ótimo humano}} & \emph{Abuso da pontuação} & \emph{Recompensas densas} & \emph{Recompensas esparsas} \\ \hline Assault & Asterix & Beam Rider & Alien & Freeway \\ Asteroids & Atlantis & Kangaroo & Amidar & Gravitar \\ Battle Zone & Berzerk & Krull & Bank Heist & Montezuma's Revenge \\ Bowling & Boxing & Kung Fu Master & Frostbite & Pitfall \\ Breakout & Centipede & Road Runner & H E R O & Private Eye \\ Chopper Cmd & Crazy Climber & Seaquest & Ms Pac Man & Solaris \\ Defender & Demon Attack & Up N Down & Q Bert & Venture \\ \hline \end{tabular}  Personally, I believe the first example is the correct one, not the second. Maybe I could get an explanation as to why latexindent prefers the second indentation? I can't see to find the logic behind it. The only customization I did to my config file is the addition of the following: lookForAlignDelims: tabular: multiColumnGrouping: 1

### cmhughes commented Oct 16, 2018

 Thanks for this. I hope to take a look at it soon. I'll report back ....

### douglasrizzo commented Oct 17, 2018

 No rush @cmhughes, it doesn't break anything and everything else is formatted accordingly. I just found it weird so I thought it better to report. Maybe the column delimiters I use, like | and ||, or the fact that I use \textbf or \emph inside \multicolumn is what's confusing latexindent?

### cmhughes commented Oct 20, 2018

 Thanks for this. I agree that your first input would be desired. I believe that it's the appearance of two different multicolumn commands that have different 'spannings' (3 and 2) which confuses things. I don't think that the | or \texbf, \emph affect this. I'll leave this open as it needs further attention, but I can't commit to investigating immediately. I'll report back at some point with updates.

### cmhughes commented Nov 3, 2018

 Thanks for this, I'm going to label it as a bug, as the current behaviour is clearly not desirable. I hope to be able to address this, but I'm not sure when that will be. Thanks again.
added the label Nov 3, 2018

### douglasrizzo commented Nov 29, 2018 • edited

 I now understand what you mean. When we have a column in our tabular environment which has intersecting multicolumn commands, each of which spans different numbers of columns, this behavior emerges. I am uploading a file which has a few examples of tables that show this kind of behavior. Extension is txt because GitHub. I used the first example as a control, so it should work fine.
changed the title Clarification regarding the behavior of multiColumnGrouping Undefined behavior when formatting vertically aligned multicolumn commands with different column spans Nov 29, 2018

### cmhughes commented Dec 1, 2018

 Thanks a lot, very helpful. I hope to take a look at this soon . Everything is a bit delayed as I'm slammed at work, but is hope to be able to look at this by early 2019....
added the label Jul 16, 2019

### cmhughes commented Jul 16, 2019

 Just to say: sorry for the delay in addressing this. It's very near (or at!) the top of my latexindent.pl priorities :)

### douglasrizzo commented Jul 19, 2019

 Hey @cmhughes glad to know you didn't forget about my issue. Just a heads-up. In one of my most recent documents, I had to add line breaks inside cells of the tabular environment. I ended up resorting to this method, which adds a nested tabular environment inside the cell we want to add line breaks to. I saw that you labelled my issue as align-at-ampersand-routine so I thought I'd warn you that, sometimes, people use nested environments and if these environments make use of ampersands to align their content, then you may have to check whether each ampersand relates to the inner or outer environments. I don't think this is directly related to my issue, but maybe this is related to #162.
added a commit that referenced this issue Mar 1, 2020
 Align at ampersand overhaul; this is motivated by the multicolumn
 0df2e13
issue reported at #143

To do: see test-cases/alignment/douglasrizzo1.tex when run with multiColumnGrouping.yaml
and then return to the more complicated version in the original issue,
above. Then ensure all test-cases behave as expected
added a commit that referenced this issue Mar 8, 2020
 Align at ampersand updated to account for the issue reported at #143.
 61b244b
Next:
- make sure that test cases behave as desired.
- can the multicolumn loops be optimised?

### cmhughes commented Mar 9, 2020

 Thanks again for this. As of 8f7836a the develop branch contains an over-hauled version of the align-at-ampersand routine. Starting with the file you gave \begin{tabular}{cc|c||c|c} \multicolumn{3}{c||}{\textbf{Exploração Fácil}} & \multicolumn{2}{c}{\textbf{Exploração Difícil}} \\ \multicolumn{2}{c|}{\emph{Ótimo humano}} & \emph{Abuso da pontuação} & \emph{Recompensas densas} & \emph{Recompensas esparsas} \\ \hline Assault & Asterix & Beam Rider & Alien & Freeway \\ Asteroids & Atlantis & Kangaroo & Amidar & Gravitar \\ Battle Zone & Berzerk & Krull & Bank Heist & Montezuma's Revenge \\ Bowling & Boxing & Kung Fu Master & Frostbite & Pitfall \\ Breakout & Centipede & Road Runner & H E R O & Private Eye \\ Chopper Cmd & Crazy Climber & Seaquest & Ms Pac Man & Solaris \\ Defender & Demon Attack & Up N Down & Q Bert & Venture \\ \hline \end{tabular}  and running latexindent.pl myfile.tex -y="lookForAlignDelims:tabular:multiColumnGrouping:1"  then you receive \begin{tabular}{cc|c||c|c} \multicolumn{3}{c||}{\textbf{Exploração Fácil}} & \multicolumn{2}{c}{\textbf{Exploração Difícil}} \\ \multicolumn{2}{c|}{\emph{Ótimo humano}} & \emph{Abuso da pontuação} & \emph{Recompensas densas} & \emph{Recompensas esparsas} \\ \hline Assault & Asterix & Beam Rider & Alien & Freeway \\ Asteroids & Atlantis & Kangaroo & Amidar & Gravitar \\ Battle Zone & Berzerk & Krull & Bank Heist & Montezuma's Revenge \\ Bowling & Boxing & Kung Fu Master & Frostbite & Pitfall \\ Breakout & Centipede & Road Runner & H E R O & Private Eye \\ Chopper Cmd & Crazy Climber & Seaquest & Ms Pac Man & Solaris \\ Defender & Demon Attack & Up N Down & Q Bert & Venture \\ \hline \end{tabular}  This will be part of the next release. Thanks again!
added the label Mar 9, 2020

### douglasrizzo commented Mar 9, 2020

 That's great! I'll make sure to do some testing when I write my next TeX document. I imagine it was rather complicated to implement.
mentioned this issue Mar 21, 2020

### cmhughes commented Mar 21, 2020

 Implemented in Version 3.8, #190
closed this Mar 21, 2020


text:
# Engineering Acoustics/Sound Absorbing Structures and Materials

 Edit this template Part 1: Lumped Acoustical Systems – 1.1 – 1.2 – 1.3 – 1.4 – 1.5 – 1.6 – 1.7 – 1.8 – 1.9 – 1.10 – 1.11 Part 2: One-Dimensional Wave Motion – 2.1 – 2.2 – 2.3 Part 3: Applications – 3.1 – 3.2 – 3.3 – 3.4 – 3.5 – 3.6 – 3.7 – 3.8 – 3.9 – 3.10 – 3.11 – 3.12 – 3.13 – 3.14 – 3.15 – 3.16 – 3.17 – 3.18 – 3.19 – 3.20 – 3.21 – 3.22 – 3.23 – 3.24

## Introduction

Noise can be defined as unwanted sound. There are many cases and applications that reducing noise level is of great importance. Loss of hearing is only one of the effects of continuous exposure to excessive noise levels. Noise can interfere with sleep and speech, and cause discomfort and other non-auditory effects. Moreover, high level noise and vibration lead to structural failures as well as reduction in life span in many industrial equipments. As an example in control valves, the vibration caused by flow instability occasionally defects the feedback to the control system and resulting in extreme oscillations. The importance of noise issue could be well understood by looking at regulations that have been passed by governments to restrict noise production in society. Industrial machinery, air/surface transportation and construction activities are assumed to be main contributors in noise production or so called "noise pollution".

## Noise Control Mechanisms

• Active Noise control

Modifying and canceling sound field by electro-acoustical approaches is called active noise control. There are two methods for active control. First by utilizing the actuators as an acoustic source to produce completely out of phase signals to eliminate the disturbances. second method is to use flexible and vibro-elastic materials to radiate a sound field interfering with the disturbances and minimize the overall intensity. The latter method is called active structural acoustic control (ASAC).

• Passive Noise Control

Passive noise control refers to those methods that aim to suppress the sound by modifying the environment close to the source. Since no input power is required in such methods, Passive noise control is often cheaper than active control, however the performance is limited to mid and high frequencies. active control works well for low frequencies hence, the combination of two methods may be utilized for broadband noise reduction.

Figure 1: Noise Control Mechanisms

## Sound Absorption

Sound waves striking an arbitrary surface are either reflected, transmitted or absorbed; the amount of energy going into reflection, transmission or absorption depends on acoustic properties of the surface. The reflected sound may be almost completely redirected by large flat surfaces or scattered by a diffused surface. When a considerable amount of the reflected sound is spatially and temporally scattered, this status is called a diffuse reflection, and the surface involved is often termed a diffuser. The absorbed sound may either be transmitted or dissipated. A simple schematic of surface-wave interactions is shown in figure 2.

Figure 2: surface-sound interaction- absorption (left), reflection (middle) and diffusing (right)

Sound energy is dissipated by simultaneous actions of viscous and thermal mechanisms. Sound absorbers are used to dissipate sound energy and to minimize its reflection [1]. The absorption coefficient ${\displaystyle \alpha }$ is a common quantity used for measuring the sound absorption of a material and is known to be the function of the frequency of the incident wave. It is defined as the ratio of energy absorbed by a material to the energy incident upon its surface.

### Sound Absorbing Coefficient

The absorbing coefficient can be mathematically presented as follows:

${\displaystyle \alpha =1-{\frac {I_{R}}{I_{I}}}}$

where α, ${\displaystyle I_{R}}$, and ${\displaystyle I_{I}}$ are the sound absorption coefficient, one-sided intensity of the reflected sound and the one-sided intensity of the incident sound, respectively.

from the above equation, it can be observed that the absorption coefficient of materials varies from 0 to 1. there are several standard methods to measure sound absorption coefficient. In one of the common approaches,a plane wave impedance tube that is equipped with two microphones is utilized.The experimental setup and dimensions are according to ASTM E1050/ISO 10534-2 [2].(Figure 3)The method is done by evaluating the transfer function, ${\displaystyle {\hat {h}}(f)}$ between two microphones spaced s apart, and a distance l from sample to get absorption coefficient using the following equations:

${\displaystyle {\hat {h}}={\frac {\hat {p_{1}}}{\hat {p_{2}}}}}$

${\displaystyle {\hat {r}}={\frac {{\hat {h}}-e^{-jks}}{e^{jks}+{\hat {h}}}}}$

${\displaystyle \alpha =1-|{\hat {r}}|^{2}}$

Where, ${\displaystyle {\hat {p_{1}}},{\hat {p_{2}}}}$ are complex pressure amplitude measured by Mic. 1 and Mic. 2 respectively. k is the wave number, s is the microphones spacing and ${\displaystyle \alpha }$ is the absorption coefficent.

According to the standard technique [2], frequency is limited by microphone spacing as well as tube diameter. It is also recommended that ${\displaystyle 0.05{\frac {c}{s}} to guarantee the plane wave propagation. The coefficient of commercial absorbing materials is specified in terms of a noise reduction coefficient (NRC) which refers to the average of absorption coefficients at 250 Hz, 500 Hz, 1,000 Hz, and 2,000 Hz. Average values of some acoustic insulating materials that are used in buildings are tabulated in table 1. Based on their construction and material structure, sound absorbers are categorized as non-porous and porous absorbers.

Figure 3: Two-microphone method to obtain sound absorption coefficient

Table 1 - Sound absorbing coefficient of common absorbents [3]
Material Sound absorption coefficient
6 mm cork sheet 0.1-0.2
6 mm porous rubber sheet 0.1-0.2
12 mm fiberboard on battens 0.3-0.4
50 mm slag wool or glass silk 0.8-0.9
Hardwood 0.3
100 mm mineral wool 0.65

### Non-Porous Absorbers ( Absorbing Resonators )

There are Two types of non-porous absorbers that are common in industrial applications. Panel (membrane) resonators and Helmholtz resonators. Panel absorbers are light, thin and non-porous sheets or membranes that are tuned to absorb sound waves over a specific frequency range. The structural resistance of the panel to fast shaping leads to sound absorption. Panel absorbers are defined by their geometry and structural vibration properties. Helmholtz Resonators or cavity absorbers are perforated structures containing very small pores; one example is the acoustic liners that are used inside the aircraft engine frame to suppress the noise emission from the compression and combustion stages. Similar structures are applied in fans and ventilators used in ventilation and air-conditioning systems. The size of the opening, the length of the neck, and the volume of the cavity govern the resonant frequency of the resonator and hence the absorption performance.

### Porous Absorbers

Porous sound absorbers correspond to materials where sound propagation takes place in a network of interconnected pores such that viscous and thermal interaction cause acoustic energy to be dissipated and converted to heat. Absorptive treatment such as mineral wool, glass fiber or high-porosity foams reduces reflection sound. Porous absorbers are in fact thermal materials and usually not effective sound barriers. The need for significant thickness compared to operating sound wavelength makes porous absorbers dramatically inefficient and impractical at low frequencies.

Figure 2: Typical variation of sound absorbing coefficient for different absorbers

## Physical Characteristic Properties of Porous Absorbers

The propagation of sound in a porous material is a phenomenon that governed by physical characteristics of a porous medium, namely porosity (${\displaystyle \phi }$) , tortuosity (q), flow resistivity (${\displaystyle \sigma }$), viscous characteristic length (${\displaystyle \Lambda }$) and thermal characteristic length(${\displaystyle \Lambda '}$).

• Porosity

Defined as the ratio of interconnected void volume (air volume in open pores) and the total volume. Most commercial absorbers have high porosity (greater than 0.95). The higher porosity the easier interaction between solid-fluid phases which leads to more sound attenuation.

${\displaystyle \phi ={\frac {V_{0}}{V_{T}}}}$

${\displaystyle V_{0}}$ = volume of the void space.

${\displaystyle V_{T}}$ = total volume of the porous material.

• Tortuosity [1]

the physical characteristics corresponds to the “non-straightness” of the pore network inside the porous material. It shows how well the porous material prevents direct flow through the porous medium. The more complex the path, the more time a wave is in contact with the absorbent and hence the more energy dissipation and more absorbing capability. If the Porous absorber is not conductive, one method to measure it is to saturate the absorbent with an electrically conducting fluid and measure the electrical resistivity of the saturated sample, ${\displaystyle R_{s}}$, and compare to the resistivity of the fluid itself, ${\displaystyle R_{f}}$ then the tortuosity can be expressed as follows:

${\displaystyle q=\phi {\frac {R_{s}}{R_{f}}}}$

• Flow resistivity

The pressure drop required to drive a unit flow through the material can be related to the viscous losses of the propagating sound waves inside the porous absorber and denoted as flow resistivity . For a wide range of porous materials, the flow resistivity is the major factor for sound absorption. The unit of flow resistance is ${\displaystyle N.s/m^{4}}$ or ${\displaystyle Rayls/m}$ and defined as the ratio of static pressure drop ${\displaystyle \Delta P}$ to a volume flow (U) for a small sample thickness (d).

${\displaystyle \sigma ={\frac {\Delta P}{Ud}}}$

• Characteristic lengths [4]

Two more important microstructural properties are the characteristic viscous length ${\displaystyle \Lambda }$ and characteristic thermal length ${\displaystyle \Lambda }$’ that contribute viscous and thermal dissipation. The former is related to smaller pores and the latter is related to the larger pores of porous aggregate. The thermal length ${\displaystyle \Lambda '}$ is the twice ratio of volume to surface area in connected pores. This is geometric and can be measured directly. The viscous length, ${\displaystyle \Lambda }$, is nearly the same, but each integral is weighted by the square of the fluid velocity v inside the pores and hence, cannot be measured directly.

${\displaystyle \Lambda '=2{\frac {\int dV}{\int dS}}}$

${\displaystyle \Lambda =2{\frac {\int v_{fluid}^{2}dV}{\int v_{fluid}^{2}dS}}}$

# Acoustic modeling of Porous Absorbents

## Wave equation in rigid porous absorbents

the plane wave equation derived from the linearized equations of conservation of mass and momentum should be modified to account for the effects of porosity, tortuosity and flow resistance. The modified wave equation[5] that governs the sound propagation in compressible-gas filled in rigid porous materials is given by:

${\displaystyle {\frac {\partial ^{2}P}{\partial x^{2}}}-({\frac {q\rho _{0}}{k_{eff}}})*{\frac {\partial ^{2}P}{\partial t^{2}}}-({\frac {\sigma \phi }{k_{eff}}})*{\frac {\partial p}{\partial t}}=0}$

where, p = sound pressure within the pores of material

${\displaystyle \rho _{0}}$ = density of compressible gas

${\displaystyle k_{eff}}$ = effective bulk modulus of the gas

q = tortuosity

${\displaystyle \phi }$ = porosity

${\displaystyle \sigma }$ = flow resistivity

The acoustical behavior of a absorptive porous layer can also be investigated from its basic acoustic quantities: the complex wave number and characteristic impedance. These quantities are obtained as a part of solution of the modified plane wave equation and can be used to determine the absorption coefficient and surface impedance. The most practical and common values for the complex wave number and the surface impedance are based on semi-empirical methods and correlated using the regression analysis. One important correlation is suggested by Delany and Bazely [6]

${\displaystyle k'=\alpha +j\beta ={\frac {\omega }{c}}[1+0.0978({\frac {\rho _{0}f}{\sigma }})^{-0.700}-j0.189({\frac {\rho _{0}f}{\sigma }})^{-0.595}]}$

${\displaystyle z'=R+jX=\rho _{0}c[1+0.0571({\frac {\rho _{0}f}{\sigma }})^{-0.754}-j0.087({\frac {\rho _{0}f}{\sigma }})^{-0.732}]}$

Where, f = frequency σ = flow resistance

## Effective Density

By assuming rigid-frame pore network in the absorbent, the solid phase would be completely motionless and the frame bulk modulus is considerably greater than that of compressible gas,hence it can be modeled as an effective fluid using the wave equation for a fluid with complex effective fluid density and complex effective bulk modulus. In this situation the dynamic density accounts for the viscous losses and the dynamic bulk modulus for the thermal losses. The effective density relation as a function of dynamic tortuosity was proposed by Johnson et al. [4]

${\displaystyle \rho _{eff}=q(1+{\frac {\sigma \phi }{j\omega \rho _{0}q}}G(\omega ))\rho _{0}}$

${\displaystyle G(\omega )={\sqrt {1+j{\frac {4q^{2}\mu \rho _{0}\omega }{\sigma ^{2}\Lambda ^{2}\phi ^{2}}}}}}$

where,

μ = gas viscosity

ω = 2πf

## Effective Bulk Module

Another factor that affects the sound propagation in the absorbent is the thermal interaction in material due to the heat exchange between the acoustic wave front traveling in the compressible fluid and the solid phase. Champoux and Allard [7]., have introduced a function ${\displaystyle G'(\omega )}$ to evaluate effective bulk module for the gas. as it is observed in the following formula this would be the function of thermal characteristic length (${\displaystyle \Lambda '}$).

${\displaystyle k_{eff}={\frac {\gamma p_{0}}{\gamma -(\gamma -1)(1-j{\frac {8\mu }{\Lambda '^{2}Pr^{2}\omega \rho _{0}}}G'(\omega ))\rho _{0}}}}$

${\displaystyle G'(\omega )={\sqrt {1+j{\frac {\Lambda '^{2}Pr^{2}\omega \rho _{0}}{16\mu }}}}}$

where,

γ = gas specific heat ratio (for air ~ 1.4)

Pr = fluid Prantdl number

## References

1. a b Cox, T. J. and P. D'antonio, Acoustic Absorbers and Diffusers, SponPress,(2004)
2. a b ASTM E1050 - 08 Standard Test Method for Impedance and Absorption of Acoustical Materials Using A Tube, Two Microphones and A Digital Frequency Analysis System
3. Link common absorbing materials, absorbing coefficients.
4. a b Johnson, D.L., Koplik, J., and Dashen, R.,"Theory of dynamic permeability and tortuosity in fluid-saturated porous media," Journal of Fluid Mechanics, vol. 176, 1987, pp. 379-402
5. Fahy, F., Foundations of Engineering Acoustics, Academic Press London, (2001).
6. Delany, M.E., and Bazley, E.N., "Acoustical properties of fibrous absorbent materials" Applied Acoustics, vol. 3, 1970, pp. 105-116.
7. Champoux, Y., and Allard, J.F., "Dynamic tortuosity and bulk modulus in air saturated porous media," Journal of Applied Physics, vol. 70, no. 4, 1991, pp. 1975-1979.


text:
# Are measurements of time and distance independent or always coupled by the speed of light

In texts about special relativity the light clock is usually described as a tool to measure time $t$. It counts how often light travels along a given distance $d$, i.e. $t = d/c$, where $c$ is the speed of light.

In other contexts, distance is defined by how far light travels in a given time $t_d$, i.e. $d = c\cdot t_d$.

Now I wonder if we have a way to define distance and time such that that not each one relies on the other one?

Is an atomic clock sufficiently different from a light clock so that we can say we do not base time measurement on distance measurement?


text:
# Hilbert number

This article is about the sequence 1, 5, 9, 13, ... For $2^{\sqrt{2}}$, see Gelfond–Schneider constant.


text:
# Irreducible representations and elementary particles

## Main Question or Discussion Point

Hi,
Namely, I've been told by teachers and read in a few texts that particles ARE irreducible representations, and I have never been able to wrap my mind around what that means.
Please keep in mind that I am no theorist or mathematician, so I may be a little loose in how I use my math jargon...

Correct me if I am wrong, but I thought particles were represented by a state vector in Hilbert space, i.e. in some particular basis an electron with a certain Hamiltonian is given by the state vector psi=(c1,c2,c3,.....) where c1, c2, c3, .... are complex.

Now, I thought that the representations of groups over some vector space were actual matrices. So if I take the group SU(2), then representations of that group would be some linear combination of the pauli matrices, since they form an irreducible representation of the group (kinda like a basis for a vector space, but instead we have matrices). I know that fermions are spin 1/2, and the spin operators in each direction (essentially the pauli matrices) are basically defined by the fact that the eigenvalues must be to +1/2, or -1/2.

This is where I get confused. I never thought of the matrices (or operators) as corresponding to particles, but instead correspond to the properties of the particles you can measure, such as the spin, energy, etc., and what I thought of the particles were the the state vectors or at least represented by them, NOT the matrices.

What do the matrices represent? There are 3 irreducible representations for SU(2), but not all three correspond to a different particle, since you can only have two, lets say an up electron or a down electron..... so does each matrix correspond to a different particle? Or is it the entire group that represents one spin half particle? Please, any clarity on the subject would be great. Thanks.

Christopher Betancourt

Related Quantum Physics News on Phys.org
You should think of infinite dimensional unitary representations of the Poincare group extended by "internal symmetries". Poincare group gives you mass and spin (or helicity), internal symmetry groups give you additional quantum numbers.

Fredrik
Staff Emeritus
Gold Member
A representation isn't a matrix. It's a group homomorphism into the group of invertible linear operators on a vector space. Suppose that F:G→GL(V) is a representation. A subspace U of V is said to be invariant if for each g in G, the range of F(g) is a subset of U. A representation F:G→GL(V) is irreducible if V doesn't have any invariant subspaces.

In QM, we're interested in unitary representations, i.e. group homomorphisms into the subgroup U(V) of GL(V) that consists of all the unitary operators. The vector space is taken to be a complex infinite-dimensional separable Hilbert space, so I'll call it H instead of V from now on. The group we're interested in (for very technical reasons) is the universal covering group of the connected part of the Poincaré group. It doesn't have a standard name, so I'll just call it G.

If F:G→U(H) is an irreducible representation (with the specific G I just mentioned), H is the Hilbert space of one-particle states of a particular species of particle.

Last edited:
So representations are maps from the group into their unitary representation? So the representation (say a fermion) would take say infinitesimal rotations and represent them as pauli matrices (or more precisely U=exp[-i*sigma/2]) over some space H where only fermions live? Are you saying the particles are the actual mapping of of a group into a unitary operator acting on the Hilbert space of that species of particle?

I'm sorry if these questions sound dumb and elementary, but this is not easy stuff to first learn

Fredrik
Staff Emeritus
Gold Member
So representations are maps from the group into their unitary representation?
Yes, I suppose you could say that, but it sounds confusing when you call the range of that map a "representation". It's the map that should be called a representation, not its range.

So the representation (say a fermion) would take say infinitesimal rotations and represent them as pauli matrices (or more precisely U=exp[-i*sigma/2]) over some space H where only fermions live?
Not infinitesimal. A unitary representation of SO(3) would take a member R of SO(3) to a unitary operator U. That unitary operator would take a state vector to the state vector that an observer rotated by R would use. When R is a rotation around an axis, let's say the z axis, by an angle θ, the unitary operator would be expressed as exp(iθJz) with Jz self-adjoint. This isn't a derived result. It is the definition of the operator Jz, the z component of "spin". Yes, this is how "spin" is defined in QM.

The Pauli matrix σz enters the picture when you consider the matrix of components of the linear operator Jz in a basis for the 2-dimensional Hilbert space that the state vectors belong to. It's 2-dimensional if we're considering an irreducible representation of SO(3) with spin 1/2.

If we instead consider an irreducible representation of (the universal covering group of the connected part of) the Poincaré group, the Hilbert space is infinite-dimensional. One of the most interesting facts about the irreducible representations is that every vector in the associated Hilbert space has the same eigenvalue of

$$P^2=\eta_{\mu\nu}P^\mu P^\nu=-(P^0)^2+\vec P^2=-H^2+\vec P^2$$

where P is the four-momentum and H is the Hamiltonian. The eigenvalue is written as -m2, and m is called the "mass" of the representation. Yes, this is how "mass" is defined in QM.

Are you saying the particles are the actual mapping of of a group into a unitary operator acting on the Hilbert space of that species of particle?
I would say that the particle species (e.g. "electron") is the real-world concept associated with a specific irreducible representation. The actual mapping is just a mapping. The unitary operator is a mapping too, but it too represents a real-world concept: The state of motion of the labratory (or equivalently, the physical system). What I mean is that the unitary operator that corresponds to a member of the universal covering group of the connected part of the Poincaré group is the mathematical representation of the physical process of rotating your lab, boosting it to another velocity, moving it to another location, and doing the experiment at a different time.

The self-adjoint operators that appear in the exponents are mathematical representations of "observables", i.e. equivalence classes of measuring devices in the real world.

You seem to be wondering what, if anything, in this mess is the mathematical representation of a specific particle. I'd say that nothing represents the actual particle, but the one-dimensional subspaces (rays) of the Hilbert space are as always mathematical representations of the real-world concept of "states", i.e. equivalence classes of preparation procedures.

...this is not easy stuff to first learn
I agree. I had to read that chapter in Weinberg's book many times, and a few other things, just to get to this level of understanding, and there are still many things I don't fully understand. (Wigner's theorem, why exactly we use the universal covering group, etc.)

So the particle fields are the irreducible reps?

Fredrik
Staff Emeritus
Gold Member
You can construct an irreducible representation by quantization of a classical field theory without interaction terms (Klein-Gordon, Dirac, Maxwell). Noether's theorem gives you a bunch of conserved quantities, and quantization turns them into self-adjoint operators, which can be used to define unitary operators. (If A is self-adjoint and s real, exp(isA) is unitary).

The representation is the function that takes members of the (universal covering group of the connected part of) the symmetry group to these unitary operators.

You can construct an irreducible representation by quantization of a classical field theory without interaction terms (Klein-Gordon, Dirac, Maxwell). Noether's theorem gives you a bunch of conserved quantities, and quantization turns them into self-adjoint operators, which can be used to define unitary operators. (If A is self-adjoint and s real, exp(isA) is unitary).

The representation is the function that takes members of the (universal covering group of the connected part of) the symmetry group to these unitary operators.
OK, so let me piece it all together....
The quantized free fields of the particle species in question ARE the irreducible representation. The irreducible reps, or fields, takes the Poincare group (Lorentz + translations?) extended by internal symmetries (gauge groups?) and maps it into unitary operators through exp(isA), where A is a hermitian operator (or self adjoint). These unitary operators in turn only act on the Hilbert space of that particular particle species whole field we are using. And those hermitian operators (A in this case) are just the operators corresponding to observable conserved quantities that we got from taking Noether's theorem and applying the symmetry operations from the Poincare group + internal symmetries to the field in question.

So to summarize,
the fields (plus Noether) gives you a prescription to turn symmetries of the extended poincare group into hermitian operators (which one can then define unitary operators from) acting on the Hilbert space of that particular species... So each Field (irr. rep.) will have a different realization of the extended poincare group (hermitian operators acting on different Hilbert spaces). And in the end we just take the different Hilbert spaces, paste them together with a direct product to construct the bigger Hilbert space (Fock space?) where the sate vector of a physical system (where many fields exist) lives.

So different particle species are just different realizations of the underlying symmetry group that governs our universe?

Is this more or less the idea? Or am I missing something?

Quantized fields are not irreducible representations. But one-particle subspaces, for stable particles, carry nearly irreducible representations of the Poincare group. Why only "nearly"? Because we have to leave the room for parities, charges, other internal degrees of freedom. So, irreducible representations of the Poincare group enter with some (usually finite) multiplicity.

Fredrik
Staff Emeritus
Gold Member
The quantized free fields of the particle species in question ARE the irreducible representation.
I wouldn't say that, especially not with emphasis on the word "are". A quantized free field can be used to explicitly construct an irreducible representation, but technically they're two very different things. A representation is a group homomorphism into the group of linear operators on a vector space. A quantized free (scalar) field is an operator-valued distribution on Minkowski spacetime.

The rest of what you said sounds good enough. I don't know how to handle gauge groups, but it looks like arkajad just told us an important part of that.

I wouldn't say that, especially not with emphasis on the word "are". A quantized free field can be used to explicitly construct an irreducible representation, but technically they're two very different things.
OK, so there are the fields, and from the fields you can construct the irreducible reps? Is there a one-to-one correspondence between the fields and the irreducible reps? Because earlier it was said that the species of a particle is its irreducible rep, but I think of a species of a particle as really just being the underlying field it comes from, so I imagine that while they are different objects, one can go back and forth between when talking about particle species.

So what would be the irreducible rep constructed from a Dirac Field (not just the spinor part)? Could you construct that mathematical object we call the irr. rep. explicitly from the field? Or can you show me a reference online that does it (Weinberg's QFT book is on its way, but now here yet)?

Fredrik
Staff Emeritus
Gold Member
Is there a one-to-one correspondence between the fields and the irreducible reps?
Probably yes. I'm not sure though.

So what would be the irreducible rep constructed from a Dirac Field (not just the spinor part)? Could you construct that mathematical object we call the irr. rep. explicitly from the field? Or can you show me a reference online that does it (Weinberg's QFT book is on its way, but now here yet)?
I don't know all the details, but ever since I learned about how particle species correspond to different irreps, I've felt that the point of quantum fields is that they give us a way to explicitly construct the irreps. But I don't know a book that actually says that, or that goes through the details of the construction. There are however many books that describe how to find the conserved quantities associated with the one-parameter subgroups, and it seems fairly straightforward to construct Lorentz transformation operators from them. (I don't have a book that does this really well, so I don't know what to recommend).

Weinberg doesn't talk much about representations after chapter 2. In his approach, the "point" of quantum fields is that if we express the interaction Hamiltonian as a combination of quantum fields, we automatically get a Lorentz invariant S-matrix.

A. Neumaier
2019 Award
OK, so there are the fields, and from the fields you can construct the irreducible reps?
No. It goes the other way: Elementary particles correspond to certain irreducible representations of the symmetry group of the universe (Poincare group times inner symmetry group - not only the gauge group but also the flavor group). These are characterized by an irreducible rep of the proper connected Poincare group,
with nonnegative mass and finite spin or helicity together with certain additional
quantum numbers.

From these irreducible reps, one can construct a corresponding free field in the way discussed in Weinberg's book. This free field classically parameterizes the possible in- or out-states of a single particle of the type described by the representation.
The corresponding quantum field describes all particles of the given kind, including their antiparticles, as long as they can be regarded as free (i.e., asymptotically, in scattering experiments).

Is there a one-to-one correspondence between the fields and the irreducible reps?
No. Only particular combinations of mass, spin/helicity, and other quantum numbers appear in Nature.

Could you construct that mathematical object we call the irr. rep. explicitly from the field? Or can you show me a reference online that does it (Weinberg's QFT book is on its way, but now here yet)?
If you have the (free) field Phi(x), with components indexed by s, say, you get the irreducible representation by taking the vacuum state |>, define |x,s>=Phi_s(x)|>,
and have the group act naturally on the 1-particle states

$$|psi> := \int dx \sum_s psi(x,s)|x,s>$$

An explicit formula for translations generators in terms of free fields can be found for instance http://arxiv.org/pdf/1008.0244" - formula (21).
Expressions for Lorentz transformations are of a similar nature. Once you have generators, you restrict them to one-particle subspace. You calculate Casimirs there and you can find mass and spin this way.

Last edited by a moderator:
If you have the (free) field Phi(x), with components indexed by s, say, you get the irreducible representation by taking the vacuum state |>, define |x,s>=Phi_s(x)|>,
and have the group act naturally on the 1-particle states

$$|psi> := \int dx \sum_s psi(x,s)|x,s>$$
So the irr. rep |psi> is the sum of all the possible combinations of states the particle can be in? This might sounds dumb then, but does that mean the irr. rep. is the Hilbert space of a particular species attached with the appropriate operators (spin, charge, etc.) corresponding to the observables of that particle species? Sorry if I am struggling, but this seems like probably the most epic thing I am learning ever, and I really want a good grasp on it (or at least SOME grasp on it).

An explicit formula for translations generators in terms of free fields can be found for instance http://arxiv.org/pdf/1008.0244" - formula (21).
Expressions for Lorentz transformations are of a similar nature. Once you have generators, you restrict them to one-particle subspace. You calculate Casimirs there and you can find mass and spin this way.
Thanks for the link, I'm reading it now, but it is a little dense.... I'll probably end up back here with more questions after reading it (once, twice, or however many times it takes).

Last edited by a moderator:
A. Neumaier


text:
We have written previously about the advantages Lightning gives exchanges and their customers. In particular; lower fees, faster transactions, and additional security. In this post we want to discuss why crypto exchanges should consider operating a routing  node on the Lightning Network and what it could mean for their business.

Lightning nodes perform two services: monitor the underlying blockchain and manage interactions with other nodes. For more detailed information about Lightning nodes and how they work, check out this post (insert nodes post). Also, check out Alex Bosworth’s video from Chaincode Labs about routing and channel management.

#### Why Exchanges Should Be Routing Nodes

Exchanges are massive hubs of cryptocurrency activity. Millions of dollars flow into and out of their platforms every day. This puts them in a position to create orders of magnitude of liquidity on the Lightning Network.  There are some tangible benefits to exchanges that manage and operate routing nodes on the Lightning Network.

Exchanges managing and operating routing nodes can earn revenue from fees paid by routing transactions along the Lightning Network. Given the large footprint of exchanges in the cryptocurrency ecosystem, they could potentially route a large volume of transactions on a daily basis. This could result in significant routing fees generated.

Node operators can charge a base fee for routing these transactions. They can change this fee for every transaction they route. Further, exchanges can set this fee to whatever they wish. While the median fee rate is currently, $.0000001, there is nothing preventing an exchange from setting a fee of$.10, $1.00,$100 or more. People may be willing to pay a premium for a node that has a proven history of routing and consistency of performance. Of course, the economics of the Lightning Network likely make it advantageous to keep fees low since high fees are a disincentive to transactions.

This fee is also flexible.  Exchanges can modify routing fees to suit their business needs; lowering or raising them as market conditions evolve. Again, this “liquidity premium” would not be immune from the economics of a mature and robust Lightning Network where there would be thousands of nodes creating liquidity and routing transactions.  The fundamental point remains the same; cryptocurrency exchanges can generate new revenue by routing transactions across the network.

The ability to collect fees could prove to be particularly useful – if not outright necessary – since exchanges will have to carefully manage their capital requirements to maintain liquidity in their channels.  It’s difficult to predict what the capital requirements might be for a node routing transactions at this early stage of the network, but it isn’t hard to imagine a scenario where routing fees are collected in relation to liquidity requirements as well as some buffer to manage channel balances.

This liquidity requirement can actually be an advantage for an exchange. Lightning integration can offer incredible speed for traders for withdrawals and deposits. For such an integration to be useful for traders, it has to be reliable. In the context of the Lightning Network, this means securing access to liquidity in channels. An exchange that invests resources into becoming a routing hub on the Lightning Network gets the added benefit of having large volumes of money flowing through their node. These funds can be used to shuffle channel balances around, making sure that traders can deposit and withdraw funds at all times. In this way becoming a routing hub has synergistic effects, where routing enables greater liquidity for withdrawals and deposits, and withdrawals and deposits generate routing fees.

Lastly, as discussed previously in our regulatory posts (Part 1 and Part 2) an exchange can always choose to simply not operate a routing node if they are concerned with violating federal or state money transmitter laws. Although we argue Lightning node operators should not be considered traditional money transmitters, it is an evolving policy issue.

#### Summary

There are compelling reasons why a cryptocurrency exchange should consider operating a routing node on the Lightning Network. It can be a source of new revenue as it routes transactions, which could be hundreds of thousands per day or more as the network grows. In addition, the funds generated from routing can in turn be used to maintain highly liquid channels for traders to make fast and easy deposits and withdrawals.  Exchanges that start exploring and learning how to operate and manage a routing node now stand to benefit the most as the Lightning Network grows.

If you’re interested in chatting more about Lightning Network technology or crypto tech in general, you can find us on Twitter @Suredbits or join our Suredbits Slack community.


text:
# Help me solve this differential equation (Capacitor Charging)

thomas49th
I'm trying to solve this:

$$E = R\frac{dQ}{dt} + \frac{Q}{C}$$

from here
http://physics.bu.edu/~duffy/semester2/c11_RC.html
You might recognize this as the charging equation for a capacitor

I'm guessing I need to try and get (1/q)dQ or similar somewhere to get the lnQ

but I cannot seem to get the right manipulation

Thanks
Thomas

Last edited:


text:
# Math Help - parametric derivative

1. ## parametric derivative

At time t, the position of a particle moving on a curve is given by
x=e^(2t)-e^(-2t) , y=3e^(2t)+e^(-2t)

(a) Find the value of t at which the curve has a horizontal tangent.
t =

(b) Find dy/dx in terms of t.
dy/dx =

(c) Find .

can somone help me do this one...plzzzzz...thanks....

mathation

2. it would be wise to find b before a. setting the derivative = 0 will give the horizontal tangent

3. $\frac{dy}{dx}=\frac{dy/dt}{dx/dt}$


text:
# Overloaded equal sign = and the word is

1. Jul 23, 2011

### Alain De Vos

Problem,the equal symbol "=" in math is overloaded , as is the word "is" in language.
Is there a list of all the meanings of = in math and the word is.
For instance "is" can mean equal to , or element of a set.
Are there generally accepted alternatives to the "=" sign, so one can be more specific.
For instance := for equal per definition.

2. Jul 23, 2011

### disregardthat

Why is it a problem that it's used extensively? As long as there is no ambiguity revolving around its use, I don't see how it could be a problem.

3. Jul 23, 2011

### Dr. Seafood

Notation is simply about communicating ideas. So in an expression like 2 + 3 = 5, it's pretty clear what "=" denotes. When talking about isomorphism, congruence or some other type of "equality", :=, ≡, ⇔, ≈, etc. are used accordingly.

I find there's no need to be more specific. Mathematics is perfectly scrutinizing as it is (I don't mean that in a bad way). These are just symbols; a good math paper would be sure that there's no ambiguity in notation.

By the way, you wouldn't say "x is S" to mean x ∈ S, right? You would say "x is in S".

4. Jul 23, 2011

### SteveL27

Actually, = is never overloaded in math.

It's an assignment operator in some programming languages; but every language that uses = for assignment uses == for equality, so there's confusion sometimes, but never overloading within a programming language or within math.

In typeset math they use $\equiv$ for mod equivalence, and $\cong$ for isomorphism. They never use = for anything but equality, as far as I know. Of course I could be wrong ... but I really don't think there are many alternate meanings or usage of = in math.

I think the main area where = is overloaded is in writing ASCII math, since there aren't any symbols for congruence, isomorphism, etc.


text:
Summary: We classify Klein links. In particular, we calculate the number and types of components in a $$K_{p,q}$$ Klein link. We completely determine which Klein links are equivalent to a torus link, and which are not.

### MSC:

 57M25 Knots and links in the $$3$$-sphere (MSC2010)


text:
A Proof of Convergence Rate of AD{}^{3}

# Alternating Directions Dual Decomposition

## Abstract

We propose AD, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs based on the alternating directions method of multipliers. Like dual decomposition algorithms, AD uses worker nodes to iteratively solve local subproblems and a controller node to combine these local solutions into a global update. The key characteristic of AD is that each local subproblem has a quadratic regularizer, leading to a faster consensus than subgradient-based dual decomposition, both theoretically and in practice. We provide closed-form solutions for these AD subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD applicable to a wide range of problems. Experiments on synthetic and real-world problems show that AD compares favorably with the state-of-the-art.

## 1 Introduction

Graphical models enable compact representations of probability distributions, being widely used in computer vision, natural language processing (NLP), and computational biology (Pearl, 1988; Lauritzen, 1996; Koller and Friedman, 2009). When using these models, a central problem is that of inferring the most probable (a.k.a. maximum a posteriori – MAP) configuration. Unfortunately, exact MAP inference is an intractable problem for many graphical models of interest in applications, such as those involving non-local features and/or structural constraints. This fact has motivated a significant research effort on approximate MAP inference.

A class of methods that proved effective for approximate inference is based on linear programming relaxations of the MAP problem (LP-MAP) (Schlesinger, 1976). Several message-passing algorithms have been proposed to address the resulting LP problems, taking advantage of the underlying graph structure (Wainwright et al., 2005; Kolmogorov, 2006; Werner, 2007; Globerson and Jaakkola, 2008; Ravikumar et al., 2010). In the same line, Komodakis et al. (2007) proposed a method based on the classical dual decomposition (Dantzig and Wolfe, 1960; Everett III, 1963; Shor, 1985), which breaks the original problem into a set of smaller subproblems; this set of subproblems, together with the constraints that they should agree on the shared variables, yields a constrained optimization problem, the Lagrange dual of which is solved using a projected subgradient method. Initially proposed for computer vision (Komodakis et al., 2007; Komodakis and Paragios, 2009), this technique has also been shown effective in several NLP tasks that involve combinatorial constraints, such as parsing and machine translation (Koo et al., 2010; Rush et al., 2010; Auli and Lopez, 2011; Rush and Collins, 2011; Chang and Collins, 2011; DeNero and Macherey, 2011). The major drawback is that the subgradient algorithm is very slow to achieve consensus in problems with a large number of overlapping components, requiring iterations for an -accurate solution. Jojic et al. (2010) addressed this drawback by introducing an accelerated method that enjoys a faster convergence rate ; however, that method is sensitive to previous knowledge of and the prescription of a temperature parameter, which may yield numerical instabilities.

In this paper, we ally the simplicity of dual decomposition (DD) with the effectiveness of augmented Lagrangian methods, which have a long-standing history in optimization (Hestenes, 1969; Powell, 1969). In particular, we employ the alternating directions method of multipliers1 (ADMM), a method introduced in the optimization community in the 1970s (Glowinski and Marroco, 1975; Gabay and Mercier, 1976) which has seen a recent surge of interest in machine learning and signal processing (Afonso et al., 2010; Mota et al., 2010; Goldfarb et al., 2010; Boyd et al., 2011). The result is a new LP-MAP inference algorithm called AD (alternating directions dual decomposition), which enjoys convergence rate. We show that AD is able to solve the LP-MAP problem more efficiently than other methods. Like the projected subgradient algorithm of Komodakis et al. (2007), AD is an iterative “consensus algorithm,” alternating between a broadcast operation, where subproblems are distributed across local workers, and a gather operation, where the local solutions are assembled by a controller. The key difference is that AD also broadcasts the current global solution, allowing the local workers to regularize their subproblems toward that solution. This has the effect of speeding up consensus, without sacrificing the modularity of DD algorithms.

Our main contributions are:

• We derive AD and establish its convergence properties, blending classical and newer results about ADMM (Glowinski and Le Tallec, 1989; Eckstein and Bertsekas, 1992; Wang and Banerjee, 2012). We show that the algorithm has the same form as the DD method of Komodakis et al. (2007), with the local MAP subproblems replaced by quadratic programs.

• We show that these AD subproblems can be solved exactly and efficiently in many cases of interest, including Ising models and a wide range of hard factors representing arbitrary constraints in first-order logic. Up to a logarithmic term, the asymptotic cost is the same as that of passing messages or doing local MAP inference.

• For factors lacking a closed-form solution of the AD subproblems, we introduce a new active set method. Remarkably, our method requires only a black box that returns local MAP configurations for each factor (the same requirement of the projected subgradient algorithm). This paves the way for using AD with large dense or structured factors, based on off-the-shelf combinatorial algorithms (e.g., Viterbi, Chu-Liu-Edmonds, Ford-Fulkerson).

• We show that AD can be wrapped into a branch-and-bound procedure to retrieve the exact MAP configuration.

AD was originally introduced by Martins et al. (2010a, 2011a) (then called DD-ADMM). In addition to a considerably more detailed presentation, this paper contains contributions that substantially extend that preliminary work in several directions: the rate of convergence, the active set method for general factors, and the branch-and-bound procedure for exact MAP inference. It also reports a wider set of experiments and the release of open-source code (available at http://www.ark.cs.cmu.edu/AD3), which may be useful to other researchers in the field.

This paper is organized as follows. We start by providing background material: MAP inference in graphical models and its LP-MAP relaxation (Section 2); the projected subgradient algorithm for the DD of Komodakis et al. (2007) (Section 3). In Section 4, we derive AD and analyze its convergence. The AD local subproblems are addressed in Section 5, where closed-form solutions are derived for Ising models and several structural constraint factors. In Section 6, we introduce an active set method to solve the AD subproblems for arbitrary factors. Experiments with synthetic models, as well as in protein design and dependency parsing (Section 7) testify for the success of our approach. Finally, related work in discussed in Section 8, and Section 9 concludes the paper.

## 2 Background

### 2.1 Factor Graphs

Let be a tuple of random variables, where each takes values in a finite set and takes values in the corresponding Cartesian product set . Graphical models (e.g., Bayesian networks, Markov random fields) are structural representations of joint probability distributions, which conveniently model statistical (in)dependencies among the variables. In this paper, we focus on factor graphs, introduced by Tanner (1981) and Kschischang et al. (2001).

###### Definition 1 (Factor graph.)

A factor graph is a bipartite graph , comprised of:

• a set of variable nodes , corresponding to the variables ;

• a set of factor nodes (disjoint from );

• a set of edges linking variable nodes to factor nodes.

For notational convenience, we use Latin letters () and Greek letters () to refer to variable and factor nodes, respectively. We denote by the neighborhood set of its node argument, whose cardinality is called the degree of the node. Formally, , for variable nodes, and for factor nodes. We use the short notation to denote the tuple of variables linked to factor , i.e., , and lowercase to denote instantiations of random variables, e.g., and .

The joint probability distribution of is said to factor according to the factor graph if it can be written as

 P(Y1=y1,…,YM=yM)∝exp(∑i∈Vθi(yi)+∑α∈Fθα(yα)), (1)

where and are called, respectively, the unary and higher-order log-potential functions. To accommodate hard constraints, we allow these functions to take values in . Fig. 1 shows examples of factor graphs with hard constraint factors (to be studied in detail in Section 5.3). For notational convenience, we represent potential functions as vectors, and , where . We denote by the vector of dimension obtained by stacking all these vectors.

### 2.2 MAP Inference

Given a factor graph , along with all the log-potential functions—which fully specify the joint distribution of —we are interested in finding an assignment with maximal probability (the so-called MAP assignment/configuration):

 ˆy ∈ argmaxy1,…,yMP(Y1=y1,…,YM=yM) (2) = argmaxy1,…,yM∑α∈Fθα(yα)+∑i∈Vθi(yi).

This combinatorial problem, which is NP-hard in general (Koller and Friedman, 2009), can be transformed into a linear program by using the concept of marginal polytope (Wainwright and Jordan, 2008), as next described. Let denote the -dimensional probability simplex,

 ΔK:={u∈RK|u≥0,1⊤u=1}=conv{e1,…,eK}, (3)

where has all entries equal to zero except for the th one, which is equal to one. We introduce “local” probability distributions over the variables and factors, and . We stack these distributions into vectors and , with dimensions and , respectively, and denote by their concatenation. We say that is globally consistent if the local distributions and are the marginals of some global joint distribution. The set of all globally consistent vectors is called the marginal polytope of , denoted as . There is a one-to-one mapping between the vertices of and the set of possible configurations : each corresponds to a vertex of consisting of “degenerate” distributions and , for each and . The MAP problem in (2) is then equivalent to the following linear program (LP):

 MAP:maximize∑α∈Fθα⊤qα+∑i∈Vθi⊤piwith respect to(p,q)∈MARG(G). (4)

The equivalence between (2) and (4) stems from the fact that any linear program on a bounded convex constraint polytope attains a solution at a vertex of that polytope (see, e.g., Rockafellar (1970)). Unfortunately, the linear program (4) is not easier to solve than (2): for a graph with cycles (which induce global consistency constraints that are hard to specify concisely), the number of linear inequalities that characterize may grow superpolynomially with the size of . As a consequence, approximations of have been actively investigated in recent years.

### 2.3 LP-MAP Inference

Tractable approximations of can be built by using weaker constraints that all realizable marginals must satisfy to ensure local consistency:

1. Non-negativity: all local marginals and must be non-negative.

2. Normalization: local marginals must be properly normalized, i.e., , for all , and , for all .

3. Marginalization: a variable participating in a factor must have a marginal which is consistent with the factor marginals, i.e., , for all and .2

Note that some of these constraints are redundant: the non-negativity of and the marginalization constraint imply the non-negativity of ; the normalization of and the marginalization constraints imply . For convenience, we express those constraints in vector notation. For each , we define a (consistency) matrix as follows:

 Miα(yi,yα)={1,if yα∼yi0,otherwise. (5)

The local marginalization constraints can be expressed as Combining all the local consistency constraints, and dropping redundant ones, yields the so-called local polytope:

 LOCAL(G)={(p,q)∈RP+Q∣∣∣qα∈Δ|Yα|,∀α∈FMiαqα=pi,∀(i,α)∈E}. (6)

The number of constraints that define grows linearly with , rather than superpolynomially. The elements of are called pseudo-marginals. Since any true marginal vector must satisfy the constraints above, is an outer approximation, i.e.,

 MARG(G)⊆LOCAL(G), (7)

as illustrated in Fig. 2.

This approximation is tight for tree-structured graphs and other special cases, but not in general (even for small graphs with cycles) (Wainwright and Jordan, 2008). The LP-MAP problem results from replacing by in (4) (Schlesinger, 1976):

 LP-MAP:maximize∑α∈Fθα⊤qα+∑i∈Vθi⊤piwith respect to(p,q)∈LOCAL(G). (8)

It can be shown that the points of that are integer are the vertices of ; therefore, the solution of LP-MAP provides an upper bound on the optimal objective of MAP.

### 2.4 LP-MAP Inference Algorithms

While any off-the-shelf LP solver can be used for solving (8), specialized algorithms have been designed to exploit the graph structure, achieving superior performance on several benchmarks (Yanover et al., 2006). Most of these specialized algorithms belong to two classes: block (dual) coordinate descent, which take the form of message-passing algorithms, and projected subgradient algorithms, based on dual decomposition.

Block coordinate descent methods address the dual of (8) by alternately optimizing over blocks of coordinates. Different choices of blocks lead to different algorithms: max-sum diffusion (Kovalevsky and Koval, 1975; Werner, 2007); max-product sequential tree-reweighted belief propagation (TRW-S) (Wainwright et al., 2005; Kolmogorov, 2006); max-product linear programming (MPLP) (Globerson and Jaakkola, 2008). These algorithms work by passing messages (that require computing max-marginals) between factors and variables. Under certain conditions, if the relaxation is tight, one may obtain optimality certificates. If the relaxation is not tight, it is sometimes possible to reduce the problem size or use a cutting-plane method to move toward the exact MAP (Sontag et al., 2008). A disadvantage of block coordinate descent algorithms is that they may stop at suboptimal solutions, since the objective is non-smooth (Bertsekas et al. 1999, Section 6.3.4).

Projected subgradient based on the dual decomposition is a classical technique (Dantzig and Wolfe, 1960; Everett III, 1963; Shor, 1985), which was first proposed in the context of graphical models by Komodakis et al. (2007) and Johnson et al. (2007). Due to its strong relationship with the approach pursued in this paper, that method is described in detail in the next section.

## 3 Dual Decomposition with the Projected Subgradient Algorithm

The projected subgradient method for dual decomposition can be seen as an iterative “consensus algorithm,” alternating between a broadcast operation, where local subproblems are distributed across worker nodes, and a gather operation, where the local solutions are assembled by a master node to update the current global solution. At each round, the worker nodes perform local MAP inference independently; hence, the algorithm is completely modular and trivially parallelizable.

For each edge , define a potential function that satisfies ; a trivial choice is . The objective (8) can be rewritten as

 ∑α∈Fθα⊤qα+∑i∈Vθi⊤pi = ∑α∈F⎛⎝θα+∑i∈N(α)M⊤iαθiα⎞⎠⊤qα, (9)

because . The LP-MAP problem (8) is then equivalent to the following primal formulation, which we call LP-MAP-P:

 LP-MAP-P:maximize∑α∈F⎛⎝θα+∑i∈N(α)M⊤iαθiα⎞⎠⊤qαwith respect toqα∈Δ|Yα|,∀α∈F,p∈RP,subject toMiαqα=pi,∀(i,α)∈E. (10)

Note that, although the -variables do not appear in the objective of (10), they play a fundamental role through the constraints in the last line, which are necessary to ensure that the marginals encoded in the -variables are consistent on their overlaps. Indeed, it is this set of constraints that complicate the optimization problem, which would otherwise be separable into independent subproblems, one per factor. Introducing a Lagrange multiplier for each of these equality constraints leads to the Lagrangian function

 L(q,p,λ) = ∑α∈F⎛⎝θα+∑i∈N(α)M⊤iα(θiα+λiα)⎞⎠⊤qα−∑(i,α)∈Eλiα⊤pi, (11)

the maximization of which w.r.t. and will yield the (Lagrangian) dual objective. Since the -variables are unconstrained, we have

 maxq,pL(q,p,λ)={g(λ)if λ∈Λ,+∞otherwise, (12)

where is the dual objective function,

 Λ:=⎧⎨⎩λ∣∣∣∑α∈N(i)λiα=0,∀i∈V⎫⎬⎭, (13)

and each is the solution of a local problem (called the -subproblem):

 gα(λ) := maxqα∈Δ|Yα|⎛⎝θα+∑i∈N(α)M⊤iα(θiα+λiα)⎞⎠⊤qα (14) = maxyα∈Yα⎛⎝θα(yα)+∑i∈N(α)(θiα(yi)+λiα(yi))⎞⎠; (15)

the last equality is justified by the fact that maximizing a linear objective over the probability simplex gives the largest component of the score vector. Finally, the dual problem is

 LP-MAP-D:minimizeg(λ)with respect toλ∈Λ. (16)

Problem (16) is often referred to as the master or controller, and each -subproblem (14)–(15) as a slave or worker. Note that each of these -subproblems is itself a local MAP problem, involving only factor . As a consequence, the solution of (14) is an indicator vector corresponding to a particular configuration (the solution of (15) ), that is, .

The dual problem (16) can be solved with a projected subgradient algorithm.3 By Danskin’s rule (Bertsekas et al., 1999, p. 717), a subgradient of is readily given by

 ∂gα(λ)∂λiα=Miαˆqα:=ˆqiα,∀(i,α)∈E; (17)

and the projection onto amounts to a centering operation. The -subproblems (14)–(15) can be handled in parallel and then have their solutions gathered for computing this projection and update the Lagrange variables. Putting these pieces together yields Algorithm 1, which assumes a black-box procedure ComputeMap that returns a local MAP assignment (as an indicator vector), given log-potentials as input. At each iteration, the algorithm broadcasts the current Lagrange multipliers to all the factors. Each factor adjusts its internal unary log-potentials (line 6) and invokes the ComputeMap procedure (line 7).4 The solutions achieved by each factor are then gathered and averaged (line 10), and the Lagrange multipliers are updated with step size (line 11). The two following propositions establish the convergence properties of Algorithm 1.

###### Proposition 2 (Convergence rate)

Let the non-negative step size sequence be diminishing and nonsummable: and . Then, Algorithm 1 converges to the solution of LP-MAP-D (16). Furthermore, iterations of Algorithm 1 are sufficient to achieve a dual objective which differs by from the optimal value.

Proof: This is a property of projected subgradient algorithms (see, e.g., Bertsekas et al. 1999).

###### Proposition 3 (Certificate of optimality)

If, at some iteration of Algorithm 1, all the local subproblems are in agreement (i.e., if after line 10, for all ), then:

• is a solution of LP-MAP-D (16);

• is binary-valued and a solution of both LP-MAP-P and MAP.

Proof: If all local subproblems are in agreement, then a vacuous update will occur in line 11, and no further changes will occur. Since the algorithm is guaranteed to converge, the current is optimal. Also, if all local subproblems are in agreement, the averaging in line 10 necessarily yields a binary vector . Since any binary solution of LP-MAP is also a solution of MAP, the result follows.

Propositions 23 imply that, if the parameters are such that LP-MAP is a tight relaxation, then Algorithm 1 yields the exact MAP configuration along with a certificate of optimality. According to Proposition 2, even if the relaxation is not tight, Algorithm 1 still converges to a solution of LP-MAP. In some problem domains, the LP-MAP is often tight (Koo and Collins, 2010; Rush et al., 2010); for problems with a relaxation gap, techniques to tighten the relaxation have been developed (Rush and Collins, 2011). However, in large graphs with many overlapping factors, it has been observed that Algorithm 1 can converge quite slowly in practice (Martins et al., 2011b). This is not surprising, given that it attempts to reach a consensus among all overlapping components; the larger this number, the harder it is to achieve consensus. In the next section, we propose a new LP-MAP inference algorithm that is more suitable for this class of problems.

## 4 Alternating Directions Dual Decomposition (AD3)

The main weaknesses of Algorithm 1 reside in the following two aspects.

1. The dual objective function is non-smooth, this being why “subgradients” are used instead of “gradients.” It is well-known that non-smooth optimization lacks some of the good properties of its smooth counterpart. Namely, there is no guarantee of monotonic improvement in the objective (see Bertsekas et al. 1999, p. 611). Ensuring convergence requires using a diminishing step size sequence, which leads to slow convergence rates. In fact, as stated in Proposition 2, iterations are required to guarantee -accuracy.

2. A close look at Algorithm 1 reveals that the consensus is promoted solely by the Lagrange multipliers (line 6). In a economic interpretation, these represent “price adjustments” that lead to a reallocation of resources. However, no “memory” exists about past allocations or adjustments, so the workers never know how far they are from consensus. It is thus conceivable that a smart use of these quantities could accelerate convergence.

To obviate the first of these problems, Johnson et al. (2007) proposed smoothing the objective function through an “entropic” perturbation (controlled by a “temperature” parameter), which boils down to replacing the in (16) by a “soft-max.” As a result, all the local subproblems become marginal (rather than MAP) computations. A related and asymptotically faster method was proposed later by Jojic et al. (2010), who address the resulting smooth optimization problem with an accelerated gradient method (Nesterov, 1983, 2005). That approach guarantees an -accurate solution after iterations, an improvement over the bound of Algorithm 1. However, those methods have some drawbacks. First, they need to operate at near-zero temperatures; e.g., the iteration bound of Jojic et al. (2010) requires setting the temperature to , which scales the potentials by and may lead to numerical instabilities in some problems. Second, the solution of the local subproblems are always dense; although some marginal values may be low, they are never exactly zero. This contrasts with the projected subgradient algorithm, for which the solutions of the local subproblems are MAP configurations. These configurations can be cached across iterations, leading to important speedups (Koo et al., 2010).

We will show that AD also yields a iteration bound without suffering from the two drawbacks above. Unlike Algorithm 1, AD broadcasts the current global solution to the workers, thus allowing them to regularize their subproblems toward that solution. This promotes a faster consensus, without sacrificing the modularity of dual decomposition. Another advantage of AD is that it keeps track of primal and dual residuals, allowing monitoring the LP-MAP optimization process and stopping when a desired accuracy level is attained.

### 4.2 Augmented Lagrangians and the Alternating Directions Method of Multipliers

Let us start with a brief overview of augmented Lagrangian methods. Consider the following general convex optimization problem with equality constraints:

 maximizef1(q)+f2(p)with respect toq∈Q,p∈Psubject toAq+Bp=c, (18)

where and are convex sets and and are concave functions. Note that the LP-MAP problem stated in (10) has this form. For any , consider the problem

 maximizef1(q)+f2(p)−η2∥Aq+Bp−c∥2with respect toq∈Q,p∈Psubject toAq+Bp=c, (19)

which differs from (18) in the extra term penalizing violations of the equality constraints; since this term vanishes at feasibility, the two problems have the same solution. The reason to consider (19) is that its objective is -strongly concave, even if is not. The Lagrangian of problem (19),

 Lη(q,p,λ)=f1(q)+f2(p)+λ⊤(Aq+Bp−c)−η2∥Aq+Bp−c∥2, (20)

is the -augmented Lagrangian of problem (18). The so-called augmented Lagrangian (AL) methods (Bertsekas et al., 1999, Section 4.2) address problem (18) by seeking a saddle point of , for some sequence . The earliest instance is the method of multipliers (MM) (Hestenes, 1969; Powell, 1969), which alternates between a joint update of and through

 (qt+1,pt+1) := argmaxq,p{Lηt(q,p,λt)|q∈Q,p∈P} (21)

and a gradient update of the Lagrange multiplier,

 λt+1 := λt−ηt(Aqt+1+Bpt+1−c). (22)

Under some conditions, this method is convergent, and even superlinear, if the sequence is increasing (Bertsekas et al. 1999, Section 4.2). A shortcoming of the MM is that problem (21) may be difficult, since the penalty term of the augmented Lagrangian couples the variables and . The alternating directions method of multipliers (ADMM) avoids this shortcoming, by replacing the joint optimization (21) by a single block Gauss-Seidel-type step:

 qt+1:=argmaxq∈QLηt(q,pt,λt)=argmaxq∈Qf1(q)+(A⊤λt)⊤q−ηt2∥Aq+Bpt−c∥2, (23)
 pt+1:=argmaxp∈PLηt(qt+1,p,λt)=argmaxp∈Pf2(p)+(B⊤λt)⊤p−ηt2∥Aqt+1+Bp−c∥2. (24)

In general, problems (23)–(24) are simpler than the joint maximization in (21). ADMM was proposed by Glowinski and Marroco (1975) and Gabay and Mercier (1976) and is related to other optimization methods, such as Douglas-Rachford splitting (Eckstein and Bertsekas, 1992) and proximal point methods (see Boyd et al. 2011 for an historical overview).

The LP-MAP-P problem (10) can be cast into the form (18) by proceeding as follows:

• let in (18) be the Cartesian product of simplices, , and ;

• let and ;

• let in (18) be a block-diagonal matrix, where , with one block per factor, which is a vertical concatenation of the matrices ;

• let be a matrix of grid-structured blocks, where the block in the th row and the th column is a negative identity matrix of size , and all the other blocks are zero;

• let .

The -augmented Lagrangian associated with (10) is

 Lη(q,p,λ)=∑α∈F(θα+M⊤iα(θiα+λiα))⊤qα−∑(i,α)∈Eλiα⊤pi−η2∑(i,α)∈E∥Miαqα−pi∥2. (25)

This is the standard Lagrangian in (11) plus the Euclidean penalty term. The ADMM updates are

 Broadcast: q(t):=argmaxq∈QLηt(q,p(t−1),λ(t−1)), (26) Gather: p(t):=argmaxp∈RPLηt(q(t),p,λ(t−1)), (27) Multiplier update: λ(t)iα:=λ(t−1)iα−ηt(Miαq(t)α−p(t)i),∀(i,α)∈E. (28)

We next analyze the broadcast and gather steps, and prove a proposition about the multiplier update.

Broadcast step. The maximization (26) can be carried out in parallel at the factors, as in Algorithm 1. The only difference is that, instead of a local MAP computation, each soft-factor worker now needs to solve a quadratic program of the form:

 maxqα∈Δ|Yα|⎛⎝θα+∑i∈N(α)M⊤iα(θiα+λiα)⎞⎠⊤qα−η2∑i∈N(α)∥Miαqα−pi∥2. (29)

The subproblem (29) differs from the linear subproblem (14)–(15) in the projected subgradient algorithm by including an Euclidean penalty term, which penalizes deviations from the global consensus. Sections 5 and 6 propose procedures to solve the local subproblems (29).

Gather step. The solution of (27) has a closed form. Indeed, this problem is separable into independent optimizations, one for each ; defining ,

 p(t)i:=argminpi∈R|Yi|∑α∈N(i)(pi−(qiα−η−1tλiα))2=|N(i)|−1∑α∈N(i)(qiα−η−1tλiα). (30)
###### Proposition 4

Let and . Then, the sequence produced by (26)–(28) satisfies

 ∑α∈N(i)λ(t)iα=0, (31) p(t)i=1|N(i)|∑α∈N(i)qiα. (32)

Proof: The proof is by induction: satisfies (31); for , if satisfies (31), then,

 ∑α∈N(i)λ(t)iα =∑α∈N(i)λ(t−1)iα−ηt⎛⎝∑α∈N(i)q(t)iα−|N(i)|p(t)i⎞⎠ =∑α∈N(i)λ(t−1)iα−ηt⎛⎝∑α∈N(i)q(t)iα−∑α∈N(i)(q(t)iα−η−1tλ(t−1)iα)⎞⎠=0,

i.e., also satisfies (31), simply by applying the update step (28).

Assembling all these pieces together leads to the AD (Algorithm 2). Notice that AD retains the modular structure of Algorithm 1: both are iterative consensus algorithms, alternating between a broadcast operation, where subproblems are distributed across local workers (lines 59 in Algorithm 2), and a gather operation, where the local solutions are assembled by a master node, which updates the global solution (line 10) and adjusts multipliers to promote a consensus (line 11). The key difference is that AD also broadcasts the current global solution to the workers, allowing them to regularize their subproblems toward that solution, thus speeding up the consensus. This is embodied in the procedure SolveQP (line 7), which replaces ComputeMAP of Algorithm 1.

### 4.4 Convergence Analysis

#### Proof of Convergence

Convergence of AD follows directly from the general convergence properties of ADMM. Remarkably, unlike in Algorithm 1 (projected subgradient), convergence is ensured with a fixed step size.

###### Proposition 5 (Convergence)

Let be the sequence of iterates produced by Algorithm 2 with a fixed . Then the following holds:

1. primal feasibility of LP-MAP-P (10) is achieved in the limit, i.e.,

 ∥Miαq(t)α−p(t)i∥→0,∀(i,α)∈E; (33)
2. the sequence converges to a solution of the LP-MAP-P (10);

3. the sequence converges to a solution of the dual LP-MAP-D (16);

4. is dual feasible, for any , thus in (16) approaches the optimum from above.

Proof: 1, 2, and 3 are general properties of ADMM (Glowinski and Le Tallec, 1989, Theorem 4.2). Statement 4 stems from Proposition 4 (simply compare (31) with (13)).

Although Proposition 5 guarantees convergence for any choice of , this parameter may strongly impact the behavior of the algorithm, as illustrated in Fig. 3. In our experiments, we dynamically adjust in earlier iterations using the heuristic described in Boyd et al. (2011), and freeze it afterwards, not to compromise convergence.

#### Primal and dual residuals

Recall from Proposition 3 that the projected subgradient algorithm yields optimality certificates, if the relaxation is tight (i.e., if the solution of the LP-MAP problem is the exact MAP), whereas in problems with a relaxation gap, it is harder to decide when to stop. It would be desirable to have similar guarantees concerning the relaxed primal.5 A general weakness of subgradient algorithms is that they do not have this capacity, being usually stopped rather arbitrarily after a given number of iterations. In contrast, ADMM allows keeping track of primal and dual residuals (Boyd et al., 2011), based on which it is possible to obtain certificates, not only for the primal solution (if the relaxation is tight), but also to terminate when a near optimal relaxed primal solution has been found. The primal residual is the amount by which the agreement constraints are violated,

 r(t)P=∑(i,α)∈E∥Miαq(t)α−p(t)i∥2∑(i,α)∈E|Yi|∈[0,1], (34)

where the constant in the denominator ensures that . The dual residual ,

 r(t)D=∑(i,α)∈E∥p(t)i−p(t−1)i∥2∑(i,α)∈E|Yi|∈[0,1], (35)

is the amount by which a dual optimality condition is violated (Boyd et al., 2011). We adopt as stopping criterion that these two residuals fall below a threshold, e.g., .

#### Approximate solutions of the local subproblems

The next proposition states that convergence may still hold, even if the local subproblems are solved approximately, provided the sequence of errors is summable. The importance of this result will be clear in Section 6, where we describe a general iterative algorithm for solving the local quadratic subproblems. Essentially, Proposition 6 allows these subproblems to be solved numerically up to some accuracy without compromising global convergence, as long as the accuracy of the solutions improves sufficiently fast over ADMM iterations.

###### Proposition 6 (Eckstein and Bertsekas, 1992)

Let , contain the exact solutions of (29), and those produced by an approximate algorithm. Then Proposition 5 still holds, provided that

 ∞∑t=1∥ˆq−~q∥<∞. (36)

#### Convergence rate

Although ADMM was invented in the 1970s, its convergence rate was unknown until recently. The next proposition states the iteration bound of AD, asymptotically equivalent to that of the algorithm of Jojic et al. (2010), therefore better than the bound of Algorithm 1.

###### Proposition 7

Assume the conditions of Proposition 5. Let be a solution of the dual problem (16), be the “averaged” Lagrange multipliers after iterations of AD, and the corresponding estimate of the dual objective. Then, after iterations, where satisfies

 C≤5η2∑i∈V|N(i)|×(1−|Yi|−1)+52η∥λ∗∥2. (37)

Proof: The proof (detailed in Appendix A) uses recent results of He and Yuan (2011) and Wang and Banerjee (2012), concerning convergence of ADMM in a variational inequality setting.

As expected, the bound (37) increases with the number of overlapping variables, the size of the sets , and the magnitude of the optimal dual vector . Note that if there is a good estimate of , then (37) can be used to choose a step size that minimizes the bound. Moreover, unlike the bound of the accelerated method of Jojic et al. (2010), which requires specifying beforehand, AD does not require pre-specifying a desired accuracy.

The bounds derived so far for all these algorithms are with respect to the dual problem—an open problem is to obtain bounds related to primal convergence.

#### Runtime and caching strategies

In practice, considerable speed-ups can be achieved by caching the subproblems, a strategy which has also been proposed for the projected subgradient algorithm (Koo et al., 2010). After a few iterations, many variables reach a consensus (i.e., ) and enter an idle state: they are left unchanged by the -update (32), and so do the Lagrange variables (28)). If at iteration all variables in a subproblem at factor are idle, then , hence the corresponding subproblem does not need to be solved. Typically, many variables and subproblems enter this idle state after the first few rounds. We will show the practical benefits of caching in the experimental section (Section 7.5).

### 4.5 Exact Inference with Branch-and-Bound

Recall that AD, as just described, solves the LP-MAP relaxation of the actual problem. In some problems, this relaxation is tight (in which case a certificate of optimality will be obtained), but this is not always the case. When a fractional solution is obtained, it is desirable to have a strategy to recover the exact MAP solution.

Two observations are noteworthy. First, as we saw in Section 2.3, the optimal value of the relaxed problem LP-MAP provides an upper bound to the original problem MAP. In particular, any feasible dual point provides an upper bound to the original problem’s optimal value. Second, during execution of the AD algorithm, we always keep track of a sequence of feasible dual points (as guaranteed by Proposition 5, item 4). Therefore, each iteration constructs tighter and tighter upper bounds. In recent work (?), we proposed a branch-and-bound search procedure that finds the exact solution of the ILP. The procedure works recursively as follows:

1. Initialize (our best value so far).

2. Run Algorithm 2. If the solution is integer, return and set to the objective value. If along the execution we obtain an upper bound less than , then Algorithm 2 can be safely stopped and return “infeasible”—this is the bound part. Otherwise (if is fractional) go to step 3.

3. Find the “most fractional” component of (call it and branch: for every , constrain and go to step 2, eventually obtaining an integer solution or infeasibility. Return the that yields the largest objective value.

Although this procedure has worst-case exponential runtime, in many problems for which the relaxations are near-exact it is found empirically very effective. We will see one example in Section 7.4.

## 5 Local Subproblems in AD3

### 5.1 Introduction

This section shows how to solve the AD local subproblems (29) exactly and efficiently, in several cases, including Ising models and logic constraint factors. These results will be complemented in Section 6, where a new procedure to handle arbitrary factors widens the applicability of AD.

By subtracting a constant from the objective (29), re-scaling, and turning the maximization into a minimization, the problem can be written more compactly as

 minimize 12∑i∈N(α)∥qiα−ai∥2−bα⊤qα with respect to qα∈Δ|Yα|,qiα∈R|Yi|,∀i∈N(α) subject to qiα=Miαqα,∀i∈N(α). (38)

where and .

We show that (5.1) has a closed-form solution or can be solved exactly and efficiently, in several cases; e.g., for Ising models, for factor graphs imposing first-order logic (FOL) constraints, and for Potts models (after binarization). In these cases, AD and the projected subgradient algorithm have (asymptotically) the same computational cost per iteration, up to a logarithmic factor.

### 5.2 Ising Models

Ising models are factor graphs containing only binary pairwise factors. A binary pairwise factor (say, ) is one connecting two binary variables (say, and ); thus and . Given that , we can write , . Furthermore, since and marginalization requires that and , we can also write