text:
If there's a single idea – a catalyst – in transforming North America's built environment, it is LEED: Leadership in Energy and Environmental Design. Created in the mid-1990s by the U.S. Green Building Council, LEED® remains the most widely-adopted green building standard in the world.
LEED represents excellence in green building design, construction, renovation, and operations and maintenance. It provides third-party verification that a building or a community uses strategies aimed at improving performance across key sustainability metrics, including energy savings, water efficiency, CO2 emissions reduction, improved indoor environmental quality, and stewardship of resources and sensitivity to their impacts. This continuously-evolving standard provides a concise framework to measure sustainability in virtually all building, community, and home project types.
LEED Version 4 launched in November 2013, increasing the threshold in energy, water, and indoor environmental quality and driving the goals of green buildings farther than ever.
Learn more about LEEDv4.
LEED in Missouri & Southern Illinois
By any measure, Missouri Gateway is a leader in LEED. Thanks to a commitment by the City of St. Louis (City Ordinance 67414), the City of Clayton, Washington University and other local institutional and corporate leaders, there are now almost 1,000 LEED Platinum, Gold, Silver, and Certified projects across the Chapter's territory. Learn more about these projects in our LEED Project Profiles.
View LEED in Missouri & Southern Illinois in a larger map
NEWSLETTER MEMBERS BLOG JOIN US
LEED Resources
USGBC: LEED
LEEDuser.com
St. Louis City Ordinance 67414
City of Clayton LEED Resolution
"In steel, glass and concrete, our Platinum-rated headquarters building epitomized the responsibility and good stewardship that has guided our company for the past 90 years. It truly reflects our corporate culture, as well as the innovative spirit of our employees."
John Alberici, Chairman of the Board, Alberici Corporation Alberici Group Headquarters, LEED Platinum, LEED NC 2.1
"We wanted to provide a good working environment. Our employees spend a lot of time here and we wanted to make sure they understood that we truly care for them."
Bob Schurwan, Vice President of Enterprise Fleet Management Enterprise Fleet Operations, LEED Silver, LEED CI 1.0 Pilot Enterprise Rent-A-Car Call Center, LEED Certified, LEED CI 2.0
"[HOK Headquarters] was HOK's second LEED-CI project (the first was a pilot) and we worked hard to meet internal requirements while maximizing sustainable opportunities. Probably the most satisfying accomplishment was initiating the Met Square building-wide recycling program as a result of our project! Nearly 5 years after completion, we still get inspired responses from visitors!"
Tim Gaidis, HOK HOK Headquarters, LEED Certified, LEED CI 1.0 Pilot


text:
There's something undoubtedly terrifying about being tipped as the buzz act for a year of music.
The weight of expectation, and subsequent pressure to live up to it, has been known to push artists into putting out records that they aren't ready – or happy – to release (Little Boots), bring on crippling panic attacks (Ellie Goulding) or simply force an artist to retreat into the studio, seemingly never to return to the public domain (Michael Kiwanuka, Daley, Jamie Woon, Clare Maguire etc. etc.)
Having been tipped in both the BBC Sound of 2013 poll, and the BRITs Critics Choice list, it's therefore no surprise that vocalist Aluna Francis and producer George Reid, known to us all as quirky electro-pop twosome AlunaGeorge, are feeling a huge sense of relief now that their debut album Body Music has been released to widespread critical acclaim. "It's actually taken a lot of the pressure off," Aluna laughs. "I'm not very good with waiting for some kind of epic day to happen. I feel pretty lucky that people have been so supportive."
One point of praise that has recurred throughout early reviews is the consistency of the album, not only in the standard of tracks (there's a total deficit of skippable numbers) but also in the maintenance of the pair's synonymous futuristic-R&B-electro-left of centre-wonky-pop aural blend. This is no coincidence – having met on MySpace back in 2009 the duo have since spent time honing and refining their sound to what it is now. "When we started working together we were just writing for the sake of it being fun and it sounding good," George explains. "In our first year of writing together we really tried everything out to end up with the sound we're working with at the moment."
Then in January of least year, everything changed. "Up until that point we had both made a lot of sacrifices as to how we led our lives. It was all just music for music's sake – which is absolutely essential but after a while you realise you need something more sustainable," Aluna cautiously recalls. Signing to major label Island Records, having been housed on Brooklyn indie label Tri Angle previously, the pair were given a Hammersmith recording studio to work out of, full time. "Rather than just two days a week, we got to spend every day in the studio. We were there any time of day, as many days as we wanted," Aluna gushes. "The fact that this was going to sustain us both creatively and as a lifestyle choice was just phenomenal. It's such an honour to be able to live off what we're doing."
In the studio, it's George who comes up with the "silly noises and random chords," and Aluna who writes the lyrics, which generally revolve around Aluna's reactions to other peoples' life stories and how she relates to them. "When I was starting out, I wrote lyrics just from my own perspective. It was very introverted," she recounts. "When you're inside your head too much your viewpoint is so narrow. You can't play with lyrics, language or get to the true nature of the subject. It's much easier to give somebody else advice." Asked whether they had to make any musical compromises after signing to a major, Aluna positively recounts "they've put a lot of good pressure on us to do what we are doing to the best of our ability. What they wanted from us was what we had to bring. They wanted more of that."
The pair has somewhat unwittingly accumulated a fan base of international proportions, through the release of a series of blog-friendly singles including 'You Know You Like It', 'Your Drums, your Love' and 'Attracting Flies'. "Playing at international festivals has been such a nice surprise for us," George reminiscences. "We had no idea what our music had been doing in other countries. We played at Sonar Festival in Barcelona and I couldn't have been more shocked by people's reactions to our music. It was the nicest feeling."
"Glastonbury also really blew us away," Aluna continues. "There's so much competition and bands are all playing at the same time. You don't know who's going to come to your tent when you're a new band. So seeing that people couldn't fit into the tent when we got there we were like, "Oh…My…God! It was incredible." In fact it is these festival memories that Aluna would consider to be her career highlight so far: "When you're at a festival and everything is wrong… it's freezing rain, wind, I'm like, "You really should be indoors," and these people are still there watching you." It is quite astonishing how genuinely grateful both Aluna and George are for their success within every answer to my questions. George's "huge career highlight" was performing on Jools Holland. "It was a moment where we realised how far we had come from where we started… It was frightening as hell." "I was absolutely beside myself with fear," Aluna laughs.
Production-wise, George's beats are most often compared to producers like Timbaland and The Neptunes. The latter isn't lost on the pair, who cite Pharrell Williams as their ultimate dream collaborator. "We're going to keep saying Pharrell and hopefully one day he will read it and he'll say, "who's this?" And we can all hang out and just have a great time", George chuckles.
Coming up the group are primarily going to be "slamming out the live shows" which they "held back quite a lot" when writing the album (although to anyone else, it would appear that the pair have been touring almost incessantly). They have the American tour coming up, followed by a stint in Japan and Australia with their 'White Noise"'collaborators, equally buzzed about production-duo Disclosure, ending with a European and British tour, proving that this is a twosome that no doubt managed to live up to their hype.
Body Music is available now through Island. Article written for The Line Of Best Fit.

redpajama_set_name: RedPajamaCommonCrawl


text:
<?php
// $Id: theme-settings.php,v 1.9 2008/09/11 09:36:51 johnalbin Exp $

// Include the definition of zen_settings() and zen_theme_get_default_settings().
include_once './' . drupal_get_path('theme', 'zen') . '/theme-settings.php';

/**
 * Implementation of THEMEHOOK_settings() function.
 *
 * @param $saved_settings
 *   An array of saved settings for this theme.
 * @return
 *   A form array.
 */
function zen_classic_settings($saved_settings) {

  // Get the default values from the .info file.
  $defaults = zen_theme_get_default_settings('zen_classic');

  // Merge the saved variables and their default values.
  $settings = array_merge($defaults, $saved_settings);

  /*
   * Create the form using Forms API: http://api.drupal.org/api/6
   */
  $form = array();
  $form['zen_classic_fixed'] = array(
    '#type'          => 'checkbox',
    '#title'         => t('Use fixed width for theme'),
    '#default_value' => $settings['zen_classic_fixed'],
    '#description'   => t('The theme should be centered and fixed at 960 pixels wide.'),
  );

  // Add the base theme's settings.
  $form += zen_settings($saved_settings, $defaults);

  // Remove some of the base theme's settings.
  unset($form['themedev']);
  //unset($form['themedev']['zen_layout']); // We don't need to select the base stylesheet.

  // Return the form
  return $form;
}

redpajama_set_name: RedPajamaGithub


Enumerates graphics adapters based on a given GPU preference.
The index of the adapter to enumerate. The indices are in order of the preference specified in GpuPreference—for example, if DXGI_GPU_PREFERENCE_HIGH_PERFORMANCE is specified, then the highest-performing adapter is at index 0, the second-highest is at index 1, and so on.
The GPU preference for the app.
The globally unique identifier (GUID) of the IDXGIAdapter object referenced by the ppvAdapter parameter.
The address of an IDXGIAdapter interface pointer to the adapter.
This parameter must not be NULL.
Returns S_OK if successful; an error code otherwise. For a list of error codes, see DXGI_ERROR.
This method allows developers to select which GPU they think is most appropriate for each device their app creates and utilizes.
This method is similar to IDXGIFactory1::EnumAdapters1, but it accepts a GPU preference to reorder the adapter enumeration. It returns the appropriate IDXGIAdapter for the given GPU preference. It is meant to be used in conjunction with the D3DCreateDevice functions, which take in an IDXGIAdapter.
When DXGI_GPU_PREFERENCE_UNSPECIFIED is specified for the GpuPreference parameter, this method is equivalent to calling IDXGIFactory1::EnumAdapters1.


Due to overwhelming demand for the Sierra REB line of two-ram balers and conveyors, Sierra International Machinery is adding a 24,000-square-foot expansion at their manufacturing facility in Jesup, Georgia. This expansion will allow Sierra the ability to increase production and meet the demand for the full Sierra product line, and is the third expansion Sierra has added to its Georgia facility since it opened in 2008.
Sierra International Machinery is proud to announce and welcome Randy Gibson as the company's Director of Sales Macpresse for the United States and Canada. Gibson will be responsible for evolving Sierra's relationship with current Sierra-Macpresse customers and building relationships with new and upcoming industries, such as RDF (refuse-derived fuel). Gibson will be assisting Sierra Regional Sales Managers in communicating the advantages of Macpresse single-ram balers and reaching out to new markets and industries that can benefit from the use of the machinery.
Introduced at ISRI 2018 this week in Las Vegas, the groundbreaking REB4 two-ram baler is the only two-ram that features Sierra's patent pending dual-compression doors. The REB4 uses 55 tons of force per door to push the material below the cutting knife and into the charging chamber, increasing charging efficiency, eliminating roll-back, and pre-densifying the material before the cycle even begins. Which leads to a 20 to 40 percent increase in production.
Sierra International's 80-2c HD automatic baler is designed specifically to handle tire wire. Units will bale tire wire and other materials, with bale sizes of 8 inches x 8 inches x variable, cycle times (empty) of 40 seconds and a hopper opening of 30 inches x 25 inches.
Sierra's REB-2 150- and 250-hp "recycle everything" balers process aluminum, extrusions, cans, stainless steel, copper, radiators and wire, as well as OCC, paper and PET. These units use twin 75-hp, 460-volt, three-phase, 60-hertz motors (twin 125-hp motors available) and provide 310 bar (4,500 psi) hydraulic system operating pressure. REB-2 balers also feature a 5-micron return-line, 3-micron kidney loop filtration, a flooded suction power unit and patent-pending, adjustable ram guides.


text:
Δ ℚuantitative √ourney
∑ Our experiences in learning quantitative applications
Persistent Homology (Part 4)
Topological Data Analysis - Part 4 - Persistent Homology¶
This is Part 4 in a series on topological data analysis. See Part 1 | Part 2 | Part 3 | Part 5
In this part we learn more about how linear algebra can help us calculate topological features in a computationally efficient manner.
Linear algebra saves the day¶
You might have noticed that calculating the homology groups and Betti numbers by hand can be very tedious and impractical for anything larger than the simple examples we've considered thus far. Fortunately, there are better ways. In particularly, we can represent most of the computation of homology groups in terms of vectors and matrices and computers are very efficient when working with vectors and matrices.
Now, we already went over what a vector is (an element in a vector space) but what is a matrix? You probably think of a matrix has a kind of 2-dimensional grid of numbers, and you know you can multiply matrices by other matrices and vectors and what not. Well a grid of numbers is certainly a convenient notation for matrices, but that's not what they are.
What's a matrix?¶
By this point, you should be comfortable with the idea of a function or map. These are both ways of translating one type of mathematical structure into another (or at least mapping one element in a structure to a different element in the same structure). In particular, we've spent a good amount of time working with boundary maps that mapped a higher-dimensional chain group to a lower dimensional chain group that preserved the structure of the original group in some way (it is a homomorphism).
So just like we can have a map between two groups, we can have a map between two vector spaces. And we call (linear) maps between vector spaces, matrices. A matrix basically applies a linear transformation on a vector space (or individual vector element) producing new vector space. A linear transformation just implies that we can only transform the vector space via the normal vector operations of scaling by a constant and addition of a constant vector.
Definition (Linear Tansformation)
More precisely, a linear transformation $M\ :\ V_1 \rightarrow V_2$ is a map $M$ from the vector spaces $V_1$ to $V_2$ such that $M(V_1 + V_2) = M(V_1) + M(V_2)$ and $M(aV_1) = aM(V_1)$ where $a$ is a scalar.
Let's say we want to map the real-valued volume $\mathbb R^3$ to the plane $\mathbb R^2$.
$$ \begin{aligned} V_1 &= span\{(1,0,0),(0,1,0),(0,0,1)\} \\ V_2 &= span\{(1,0),(0,1)\} \end{aligned} $$
Now, what if I want to map $V_1$ to $V_2$, that is, I want to send every point in $V_1$ to a point in $V_2$. There are many reasons why I might want to do something like this. If I'm making a graphics application, for example, I want to offer an option to rotate images drawn, and this is simply a matter of applying a linear transformation on the pixels.
So we want a map $M : V_1 \rightarrow V_2$, and we'll call this map a matrix. Notice that $V_1$ has a basis with 3 elements, and $V_2$ has a basis with 2 elements. In order to map from one space to the other, we just need to map one basis set to another basis set. And remember, since this is a linear map, all we are allowed to do to a basis is multiply it by a scalar or add another vector to it; we can't do exotic things like square it or take the logarithm.
Let's call the 3 basis elements of $V_1: B_1, B_2, B_3$. Hence, $V_1 = \langle{B_1, B_2, B_3}\rangle$. Similarly, we'll call the 2 basis elements of $V_2: \beta_1, \beta_2$. Hence, $V_2 = \langle{\beta_1, \beta_2}\rangle$. (Remember the angle brackets $\langle\rangle$ mean span, i.e. the set of all linear combinations of those elements). We can setup equations such that any vector in $V_1$ can be mapped to a vector in $V_2$ by using the fact that each vector space can be defined by their bases.
New Notation (Vector)
To prevent confusion between symbols that refer to scalars and symbols that refer vectors, I will henceforth add a little arrow over every vector $\vec{v}$ to denote it is a vector, not a scalar. Remember, the scalar is just a single element from the underlying field $F$ over which the vector space is defined.
We can define our map $M(V_1) = V_2$ in this way:
$$ \begin{aligned} M(B_1) &= a\vec \beta_1 + b\vec \beta_2 \mid a,b \in \mathbb R \\ M(B_2) &= c\vec \beta_1 + d\vec \beta_2 \mid c,d \in \mathbb R \\ M(B_3) &= e\vec \beta_1 + f\vec \beta_2 \mid e,f \in \mathbb R \\ \end{aligned} $$
That is, the map from each basis in $V_1$ is setup as a linear combination of the basis elements in $V_2$. This requires us to define a total of 6 new pieces of data: $a,b,c,d,e,f \in \mathbb R$ required for our mapping. We just have to keep track of the fact that $a,b$ are for mapping to $\beta_1$ and $d,e,f$ are for mapping to $\beta_2$. What's a convenient way to keep track of all of that? Oh I know, a matrix!
$$ M = \begin{pmatrix} a & c & e \\ b & d & f \\ \end{pmatrix} $$
That is a very convenient way to represent our map $M\ :\ V_1 \rightarrow V_2$ indeed. Notice that each column of this matrix corresponds to the "mapping equation" coefficients for each M(B_n). Also notice that the dimensions of this matrix, $2\times3$, corresponds to the dimensions of the two vector spaces we're mapping to and from. That is, any map $\mathbb R^n \rightarrow \mathbb R^m$ will be represented as an $m\times n$ matrix. It is important to keep in mind that since the linear map (and hence the matrix) depend on coefficients applied to a basis, then the matrix elements will change if one uses a different basis.
Knowing this we can easily see how vector-matrix multiplication should work and why the dimensions of a matrix and vector have to correspond. Namely, a $n \times m$ vector/matrix multiplied by a $j \times k$ vector/matrix must produce a $n \times k$ vector/matrix, and for it to work at all, $m = j$.
This is how we can multiply our matrix map $M$ by any vector in $V_1$ to produce the mapped-to vector in $V_2$:
M(\vec v\ \in\ V_1)¶
\underbrace{ \begin{bmatrix} a & c & e \\ b & d & f \\ \end{bmatrix}}_{M:V_1\rightarrow V_2} \underbrace{ \begin{pmatrix} x \ y \ z \
\end{pmatrix}}_{\vec v\ \in\ V_1}¶
\underbrace{ \begin{bmatrix} a x & c y & e z \ b x & d y & f z \
\end{bmatrix}}_{M:V_1\rightarrow V_2}¶
\begin{pmatrix} a * x + c * y + e * z \\ b * x + d * y + f * z \\ \end{pmatrix} $$
Ok now we know a matrix is a linear map between two vector spaces. But what happens if you multiply two matrices together? Well that is just a composition of maps. For example, we have three vector spaces $T, U, V$ and two linear maps $m_1, m_2$:
$$ T \stackrel{m_1}{\rightarrow} U \stackrel{m_2}{\rightarrow} V$$
To get from $T$ to $V$, we need to apply both maps: $m_2(m_1(T)) = V$. Hence, multiplying two matrices together gives us a composition of maps $m_2 \circ m_1$. The identity matrix is an identity map (i.e. it doesn't change the input) that takes the form where 1s are along the diagonal and 0s everywhere else, e.g.:
$$ m= \begin{bmatrix} \ddots & 0 & 0 & 0 & ⋰ \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ ⋰ & 0 & 0 & 0 & \ddots \\ \end{bmatrix} \\ m \vec V = \vec V $$
Back to simplicial homology (again)¶
We learned all of that so we can represent the boundary map $\partial(C_n)$ as a matrix so we can apply the tools of linear algebra. This makes sense since we already know that the chain groups $C_n$ can be viewed as vector spaces when we allow scalar multiplication, so then a linear map between the chain vector spaces is the boundary map, that we can represent as a matrix.
We represent an $n$-boundary map, i.e. $\partial(C_n)$, where $n$ is the dimension of the chain group, $k$ is the number of simplices in $C_n$ and $l$ is the number of simplices in $C_{n-1}$, as a matrix with $k$ columns and $l$ rows. Thus each column represents a simplex in $C_n$ and each row represents a simplex in $C_{n-1}$. We put a $1$ in a cell of the matrix if the simplex in that column maps to the simplex in that row. For example, $\partial([a,b]) = a - b$ if the field is $\mathbb Z$, so we will put a $1$ in the row for $a$ and $b$ since the 1-simplex $[a,b]$ maps to those two 0-simplices.
Let's try calculating the homology groups of the previous simplicial complex (depicted below again) using matrices and vectors. We're going to go back to using $\mathbb Z_2$ as our field (so simplex orientation can be ignored) because it is computationally more efficient to do so.
$$ S = \text{ {[a], [b], [c], [d], [a, b], [b, c], [c, a], [c, d], [d, b], [a, b, c]} } $$
Since we're using the (very small) finite field $\mathbb Z_2$ then we can actually list out all the vectors in our chain (group) vector space. We have 3 chain groups, namely the group of 0-simplices (vertices), 1-simplices (edges), and 2-simplices (triangle).
In our example, we only have a single 2-simplex: [a,b,c], thus the group it generates over the field $\mathbb Z_2$ is only $\{0, [a,b,c]\}$ which is isomorphic to $\mathbb Z_2$. Recall, in general, the group generated by the number $n$ of $p$-simplices in a simplicial complex is isomorphic to $\mathbb Z^n_2$. For a computer to understand, we can encode the group elements just using their coefficients 1 or 1. So, for example, the group generated by $[a,b,c]$ can just be represented as $\{0,1\}$. Or the group generated by the 0-simplices $\{a, b, c, d\}$ can be represented by 4-dimensional vectors, for example, if a group element is $a+b+c$ then we encode this as $(1, 1, 1, 0)$ where each position represents the presence or abscence of $(a, b, c, d)$, respectively.
Here are all the chain groups represented as vectors with just coefficients (I didn't list all elements for $C_1$ since there are so many [32]):
$$ \begin{align} C_0 &= \left\{ \begin{array}{ll} (0,0,0,0) & (1,0,0,0) & (0,1,1,0) & (0,1,0,1) \\ (0,1,0,0) & (0,0,1,0) & (0,0,1,1) & (0,1,1,1) \\ (0,0,0,1) & (1,1,0,0) & (1,0,0,1) & (1,0,1,1) \\ (1,1,1,0) & (1,1,1,1) & (1,0,1,0) & (1,1,0,1) \\ \end{array} \right. & \cong \mathbb Z^4_2 \\ C_1 &= \left\{ \begin{array}{ll} (0,0,0,0,0) & (1,0,0,0,0) & (0,1,1,0,0) & (0,1,0,1,0) \\ (0,1,0,0,0) & (0,0,1,0,0) & (0,0,1,1,0) & (0,1,1,1,0) \\ \dots \end{array} \right. & \cong \mathbb Z^5_2 \\ C_2 &= \left\{ \begin{array}{ll} 0 & 1 \end{array} \right. & \cong \mathbb Z_2 \end{align} $$
To represent the boundary map (which is a linear map) of the group of $p$-simplices as a matrix, we set the columns to represent each $p$-simplex in the group, and the rows represent each $(p-1)$-simplex. We put a $1$ in each position of the matrix if the $(p-1)$-simplex row is a face of the $p$-simplex column.
We index rows and columns as an ordered pair $(i, j)$ respectively. Thus the element $a_{2,3}$ is the element in the 2nd row (from the top) and the 3rd column (from the left).
The generic boundary matrix is thus (each column is a $p$-simplex, each row is a $(p-1)$-simplex):
$$ \begin{align} \partial_p &= \begin{pmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1,j} \\ a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{2,j} \\ a_{3,1} & a_{3,2} & a_{3,3} & \cdots & a_{3,j} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{i,1} & a_{i,2} & a_{i,3} & \cdots & a_{i,j} \end{pmatrix} \end{align} $$
We'll start by representing the boundary map $\partial(C_2)$ as a matrix. There's only one 2-simplex in $C_2$ so there is only one column, but there are five 1-simplices in $C_1$ so there are 5 rows.
\partial_2 ¶
\begin{array}{c|lcr} \partial & [a,b,c] \\ \hline [a,b] & 1 \\ [b,c] & 1 \\ [c,a] & 1 \\ [c,d] & 0 \\ [d,b] & 0 \\ \end{array} $$
We put a $1$ if each row-element was a face of the simplex $[a,b,c]$. This matrix makes sense as a linear map because if we multiply it by a vector element in $C_2$ (there's only 1, besides the 0 element) we get what we expect:
$$ \begin{align} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ \end{pmatrix} * 0 \qquad &= \qquad \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} \\ \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ \end{pmatrix} * 1 \qquad &= \qquad \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ \end{pmatrix} \end{align} $$
Okay, let's move on to building the boundary matrix $\partial(C_1)$:
$$ \partial_1 = \begin{array}{c|lcr} \partial & [a,b] & [b,c] & [c,a] & [c,d] & [d,b] \\ \hline a & 1 & 0 & 1 & 0 & 0 \\ b & 1 & 1 & 0 & 0 & 1 \\ c & 0 & 1 & 1 & 1 & 0 \\ d & 0 & 0 & 0 & 1 & 1 \\ \end{array} $$
Does this make sense? Let's check with some python/numpy. Let's take an arbitrary element from the group of 1-chains, namely: $[a,b]+[c,a]+[c,d]$ which we've encoded as $(1,0,1,1,0)$ and apply the boundary matrix and see what we get.
b1 = np.matrix([[1,0,1,0,0],[1,1,0,0,1],[0,1,1,1,0],[0,0,0,1,1]]) #boundary matrix C_1
el = np.matrix([1,0,1,1,0]) #random element from C_1
np.fmod(b1 * el.T, 2) # we want integers modulo 2
matrix([[0],
[1],
[1]])
$\require{cancel}$
Recall that $(0,1,0,1)$ translates to $b+d$. By hand we can calculate the boundary and compare: $$\partial([a,b]+[c,a]+[c,d]) = a+b+c+a+c+d = \cancel{a}+b+\cancel{c}+\cancel{a}+\cancel{c}+d = b+d = (0,1,0,1)$$
Lastly, we need the boundary matrix for $C_0$ which is trivial since the boundary of $0$-simplices always maps to $0$, so $$ \partial_0 = \begin{pmatrix} 0 & 0 & 0 & 0 \\ \end{pmatrix} $$
Okay, now we have our three boundary matrices, how do we calculate the Betti numbers? Well recall that sequence of subgroups of a chain group: $ B_n \leq Z_n \leq C_n $ which are the group of boundaries, group of cycles, and chain group, respectively.
Also recall that Betti $b_n = dim(Z_n\ /\ B_n)$. But that's when things were represented as just sets with group structure, now everything is represented as vectors and matrices, so instead we define the Betti number $b_n = rank(Z_n)\ -\ rank(B_n)$. What does rank mean? Rank and dimension are related but not the same. If we think of the columns of a matrix as a set basis vectors: $\beta_1, \beta_2, \dots \beta_k$ then the dimension of the span of those column vectors $\langle \beta_1, \beta_2, \dots \beta_k \rangle$ is the rank of the matrix. It turns out that you can also use the rows and it will have the same result. Importantly, however, dimension is defined on the smallest set of basis elements, i.e. the basis elements that are linearly independent.
The boundary matrix $\partial_n$ contains the information for the chain group and cycles subgroup, and the $B_{n-1}$ boundary subgroup, all the information we need to calculate the Betti number. Unfortunately, in general, our naïve approach of building the boundary matrix is not in a form where the group and subgroup information is readily accessible. We need to modify the boundary matrix, without disturbing the mapping information it contains, into a new form called Smith normal form. Basically, the smith normal form of a matrix will have $1$s along the diagonal starting from the top left of the matrix and $0$s everywhere else.
For example, $$ \begin{align} \text{Smith normal form} &:\ \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & ? \end{pmatrix} \end{align} $$
Notice the $1$s along the diagonal do not necessarily need to extend all the way down to the bottom right. And here's the information available once it's in Smith normal form (the red diagonal box indicates the $1$s): (Source: "COMPUTATIONAL TOPOLOGY" by Edelsbrunner and Harer, pg. 104)
So how do we get a matrix into Smith normal form? We do so by playing a game involving manipulating the matrix according to some rules. Here are the two allowed operations on the matrix:
You can swap any two columns or any two rows in the matrix.
You can add a column to another column, or a row to another row.
Now you just need to apply these operations until you get the matrix in Smith normal form. I should point out that this process is alot easier when we use the field $\mathbb Z_2$. Let's try it out on the boundary matrix for $C_1$.
We already have 1s across the diagonal, but we have a lot of 1s not along the diagonal.
Steps: Add column 3 to 5, then add column 4 to 5, then add column 5 to 1, then swap columns 1 and 5: $$ \partial_1 = \begin{pmatrix} 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} $$
Steps: Add column 1 to 3, add column 2 to 3, swap columns 3 and 4, add row 1 to 2, add row 4 to 2, add row 3 to 2, add row 4 to 3, swap rows 3 and 2, swap rows 4 and 3. Stop. $$ \text{Smith normal form: } \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} $$ Once we have the matrix in Smith normal form, we don't do any more operations. We could of course continue adding rows and columns together until we get a matrix of only 0s, but that wouldn't be very helpful! I sort of randomly added rows/columns to get it into the Smith normal form, but there really is an algorithm that can do it relatively efficiently.
Rather than walk through the detailed implementation of the Smith normal form algorithm, I will merely use an existing algorithm:
def reduce_matrix(matrix):
#Returns [reduced_matrix, rank, nullity]
if np.size(matrix)==0:
return [matrix,0,0]
m=matrix.shape[0]
n=matrix.shape[1]
def _reduce(x):
#We recurse through the diagonal entries.
#We move a 1 to the diagonal entry, then
#knock out any other 1s in the same  col/row.
#The rank is the number of nonzero pivots,
#so when we run out of nonzero diagonal entries, we will
#know the rank.
nonzero=False
#Searching for a nonzero entry then moving it to the diagonal.
for i in range(x,m):
for j in range(x,n):
if matrix[i,j]==1:
matrix[[x,i],:]=matrix[[i,x],:]
matrix[:,[x,j]]=matrix[:,[j,x]]
nonzero=True
if nonzero:
#Knocking out other nonzero entries.
for i in range(x+1,m):
if matrix[i,x]==1:
matrix[i,:] = np.logical_xor(matrix[x,:], matrix[i,:])
for i in range(x+1,n):
if matrix[x,i]==1:
matrix[:,i] = np.logical_xor(matrix[:,x], matrix[:,i])
#Proceeding to next diagonal entry.
return _reduce(x+1)
#Run out of nonzero entries so done.
return x
rank=_reduce(0)
return [matrix, rank, n-rank]
# Source: < https://triangleinequality.wordpress.com/2014/01/23/computing-homology/ >
reduce_matrix(b1)
#Returns the matrix in Smith normal form as well as rank(B_n-1) and rank(Z_n)
[matrix([[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0]]), 3, 2]
As you can see we got the same result by hand, but surely the algorithm was more efficient.
Since each boundary map gives us $Z_n$ (cycles) and $B_{n-1}$ (boundary for (n-1)-chain group) we need both $\partial_n$ and $\partial_{n+1}$ in order to calculate the Betti number for chain group $n$. Remember, we now calculate Betti numbers as
Betti $b_n = rank(Z_n) - rank(B_n)$
Let's start calculating those Betti numbers.
#Initialize boundary matrices
boundaryMap0 = np.matrix([[0,0,0,0]])
boundaryMap1 = np.matrix([[1,0,1,0,0],[1,1,0,0,1],[0,1,1,1,0],[0,0,0,1,1]])
boundaryMap2 = np.matrix([[1,1,1,0,0]])
#Smith normal forms of the boundary matrices
smithBM0 = reduce_matrix(boundaryMap0)
#Calculate Betti numbers
betti0 = (smithBM0[2] - smithBM1[1])
betti2 = 0  #There is no n+1 chain group, so the Betti is 0
print(smithBM0)
print("Betti #0: %s \n Betti #1: %s \n Betti #2: %s" % (betti0, betti1, betti2))
[matrix([[0, 0, 0, 0]]), 0, 4]
[matrix([[1, 0, 0, 0, 0]]), 1, 4]
Betti #0: 1
Great it worked!
But we skipped an important step. We designed the boundary matrices by hand initially, in order to algorithm-ize the entire process from building a simplicial complex over data to computing Betti numbers, we need an algorithm that takes a simplicial complex and builds the boundary matrices. Let's tackle that now.
In [138]:
#return the n-simplices in a complex
def nSimplices(n, complex):
nchain = []
for simplex in complex:
if len(simplex) == (n+1):
nchain.append(simplex)
if (nchain == []): nchain = [0]
return nchain
#check if simplex is a face of another simplex
def checkFace(face, simplex):
if simplex == 0:
elif set(face) < set(simplex): #if face is a subset of simplex
#build boundary matrix for dimension n ---> (n-1) = p
def boundaryMatrix(nchain, pchain):
bmatrix = np.zeros((len(nchain),len(pchain)))
for nSimplex in nchain:
for pSimplex in pchain:
bmatrix[i, j] = checkFace(pSimplex, nSimplex)
return bmatrix.T
Those are very simple helper functions that we'll use to build the boundary matrix and then use the previously described reduction algorithm to get it into Smith normal form. Remember, the simplicial complex example we're using looks like this: I've just replaced {a,b,c,d} with {0,1,2,3} so Python can understand it.
S = [{0}, {1}, {2}, {3}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2}] #this is our simplex from above
chain2 = nSimplices(1, S)
reduce_matrix(boundaryMatrix(chain2, chain1))
Out[139]:
[array([[ 1.,  0.,  0.,  0.,  0.],
[ 0.,  1.,  0.,  0.,  0.],
[ 0.,  0.,  0.,  0.,  0.]]), 3, 2]
Now let's put everything together and make a function that will return all the Betti numbers of a simplicial complex.
def betti(complex):
max_dim = len(max(complex, key=len)) #get the maximum dimension of the simplicial complex, 2 in our example
betti_array = np.zeros(max_dim) #setup array to store n-th dimensional Betti numbers
z_n = np.zeros(max_dim) #number of cycles (from cycle group)
b_n = np.zeros(max_dim) #b_(n-1) boundary group
for i in range(max_dim): #loop through each dimension starting from maximum to generate boundary maps
bm = 0 #setup n-th boundary matrix
chain2 = nSimplices(i, complex) #n-th chain group
if i==0: #there is no n+1 boundary matrix in this case
bm = 0
z_n[i] = len(chain2)
b_n[i] = 0
chain1 = nSimplices(i-1, complex) #(n-1)th chain group
bm = reduce_matrix(boundaryMatrix(chain2, chain1))
z_n[i] = bm[2]
b_n[i] = bm[1] #b_(n-1)
for i in range(max_dim): #Calculate betti number: Z_n - B_n
if (i+1) < max_dim:
betti_array[i] = z_n[i] - b_n[i+1]
betti_array[i] = z_n[i] - 0 #if there are no higher simplices, the boundary group of this chain is 0
return betti_array
Alright, no we should have everything we need to calculate the set of Betti numbers on any arbitrary simplicial complex given in the right format. Keep in mind that all this code is for learning purposes so I've kept it intentionally simple. It is not production ready. It has basically no safety checks so it will just fail if it gets something even slightly unexpected.
But let's see how versatile our procedure is by trying it out on various simplicial complexes.
Let $H = \text{ { {0}, {1}, {2}, {3}, {4}, {5}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2} } }$
As you can tell this is the same simplicial complex we've been working with except now it has a disconnected edge on the right. Thus we should get Betti=2 for dimension 0 since there are 2 connect components.
H = [{0}, {1}, {2}, {3}, {4}, {5}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2}]
betti(H)
array([ 2.,  1.,  0.])
Let's try another one, now with 2 cycles and 2 connect components.
Let $Y_1 = \text{ { {0}, {1}, {2}, {3}, {4}, {5}, {6}, {0, 6}, {2, 6}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2} } }$
Y1 = [{0}, {1}, {2}, {3}, {4}, {5}, {6}, {0, 6}, {2, 6}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2}]
betti(Y1)
Here's another. I just added a stranded vertex:
Let $Y_2 = \text{ { {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {0, 6}, {2, 6}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2} } }$
Y2 = [{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {0, 6}, {2, 6}, {4, 5}, {0, 1}, {1, 2}, {2, 0}, {2, 3}, {3, 1}, {0, 1, 2}]
One last one. This is a hollow tetrahedron:
D = [{0}, {1}, {2}, {3}, {0,1}, {1,3}, {3,2}, {2,0}, {2,1}, {0,3}, {0,1,3}, {0,1,2}, {2,0,3}, {1,2,3}]
betti(D)
Exactly what we expect! Okay, it looks like we can reliably calculate Betti numbers for any arbitrary simplicial complex.
What's next?¶
These first 4 posts were all just exposition on the math and concepts behind persistent homology, but so far all we've done is (non-persistent) homology. Remember back in part 2 where we wrote an algorithm to build a simplicial complex from data? Well recall that we needed to arbitrarily choose a parameter $\epsilon$ that determined whether or not two vertices were close enough to connect with an edge. If we set a small $\epsilon$ then we'd have a very dense graph with a lot of edges, if we chose a large $\epsilon$ then we'd get a more sparse graph.
The problem is we have no way of knowing what the "correct" $\epsilon$ value should be. We will get dramatically different simplicial complexes (and thus different homology groups and Betti numbers) with varying levels of $\epsilon$. Persistent homology basically says: let's just continuously scale $\epsilon$ from 0 to the maximal value (where all vertices are edge-wise connected) and see which topological features persist the longest. We then believe that topological features (e.g. connected components, cycles) that are short-lived across scaling $\epsilon$ are noise whereas those that are long-lived (i.e. persistent) are real features of the data. So next time we will work on modifying our algorithms to be able to continuously vary $\epsilon$ while tracking changes in the calculated homology groups.
References (Websites):¶
http://dyinglovegrape.com/math/topology_data_1.php
http://www.math.uiuc.edu/~r-ash/Algebra/Chapter4.pdf
https://en.wikipedia.org/wiki/Group_(mathematics)
https://jeremykun.com/2013/04/03/homology-theory-a-primer/
http://suess.sdf-eu.org/website/lang/de/algtop/notes4.pdf
http://www.mit.edu/~evanchen/napkin.html
https://triangleinequality.wordpress.com/2014/01/23/computing-homology
References (Academic Publications):¶
Basher, M. (2012). On the Folding of Finite Topological Space. International Mathematical Forum, 7(15), 745–752. Retrieved from http://www.m-hikari.com/imf/imf-2012/13-16-2012/basherIMF13-16-2012.pdf
Day, M. (2012). Notes on Cayley Graphs for Math 5123 Cayley graphs, 1–6.
Doktorova, M. (2012). CONSTRUCTING SIMPLICIAL COMPLEXES OVER by, (June).
Edelsbrunner, H. (2006). IV.1 Homology. Computational Topology, 81–87. Retrieved from http://www.cs.duke.edu/courses/fall06/cps296.1/
Erickson, J. (1908). Homology. Computational Topology, 1–11.
Evan Chen. (2016). An Infinitely Large Napkin.
Grigor'yan, A., Muranov, Y. V., & Yau, S. T. (2014). Graphs associated with simplicial complexes. Homology, Homotopy and Applications, 16(1), 295–311. http://doi.org/10.4310/HHA.2014.v16.n1.a16
Kaczynski, T., Mischaikow, K., & Mrozek, M. (2003). Computing homology. Homology, Homotopy and Applications, 5(2), 233–256. http://doi.org/10.4310/HHA.2003.v5.n2.a8
Kerber, M. (2016). Persistent Homology – State of the art and challenges 1 Motivation for multi-scale topology. Internat. Math. Nachrichten Nr, 231(231), 15–33.
Khoury, M. (n.d.). Lecture 6 : Introduction to Simplicial Homology Topics in Computational Topology : An Algorithmic View, 1–6.
Kraft, R. (2016). Illustrations of Data Analysis Using the Mapper Algorithm and Persistent Homology.
Lakshmivarahan, S., & Sivakumar, L. (2016). Cayley Graphs, (1), 1–9.
Liu, X., Xie, Z., & Yi, D. (2012). A fast algorithm for constructing topological structure in large data. Homology, Homotopy and Applications, 14(1), 221–238. http://doi.org/10.4310/HHA.2012.v14.n1.a11
Naik, V. (2006). Group theory : a first journey, 1–21.
Otter, N., Porter, M. A., Tillmann, U., Grindrod, P., & Harrington, H. A. (2015). A roadmap for the computation of persistent homology. Preprint ArXiv, (June), 17. Retrieved from http://arxiv.org/abs/1506.08903
Semester, A. (2017). § 4 . Simplicial Complexes and Simplicial Homology, 1–13.
Singh, G. (2007). Algorithms for Topological Analysis of Data, (November).
Zomorodian, A. (2009). Computational Topology Notes. Advances in Discrete and Computational Geometry, 2, 109–143. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.7483
Zomorodian, A. (2010). Fast construction of the Vietoris-Rips complex. Computers and Graphics (Pergamon), 34(3), 263–271. http://doi.org/10.1016/j.cag.2010.03.007
Symmetry and Group Theory 1. (2016), 1–18. http://doi.org/10.1016/B978-0-444-53786-7.00026-5
posted at 00:35 by Brandon Brown · Topological Data Analysis · TDA persistent-homology