Cynosure对《Discrete Calculus》的笔记(1)

第1页

符号：
N($_1$)($^T$) = A($^T$)  : the node–edge incidence matrix 
N($_2$)($^T$) = B($^T$)  :  the edge–face incidence matrix.
σ($^p$): p-cell
Bp： p-ball
∂Bp
V：0-cells or nodes,
E：1-cells or edges
F：2-cells or faces

C($_p$): the space of p-chain
σ($_i$): p-chain basis
τ($_p$): p-chain
C($^p$): the space of p-cochain
σ($^i$): p-cochain basis
c($^p$): p-cochain

p-simplex: a p-cell consists of exactly p+1 vertices
p-clique: a clique comprised of p nodes C($^p$): vector space of p-cochains

diag(v) ：矩阵，该矩阵以向量v为对角线上的元素
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discrete Calculus
.
（conventional (连续的)vector calculus 以下简记为vector calculus，与discrete calculus相对。）
.
discrete calculus
complex networks
algorithmic content extraction
.
1.1 Discrete Calculus
It establishes a separate, equivalent calculus that operates purely in the discrete space without any reference to an underlying continuous process.
.
It aims to establish a fully discrete calculus rather than a discretized calculus
(discretized calculus后来发展成为finite element method；进一步(把点变成cell complex)发展为mimetic discretization) )
Discrete Calculus不是传统微积分的离散化，历史上两者平行发展，两者的出发点：
- spatial representations and relationships
- the description of physical systems associated with space
.
The standard setting for this discrete calculus is a cell complex, of which a graph or network is a
special case.
.
1.1.1 Origins of Vector Calculus(传统微积分)
infinitesimal 但微积分基本定理却不依赖于infinitesimal（微积分基本定理本质上描述的是topological relationship）
.
1D calculus----(2D complex number: a+ib)-------------------->2D calculus
–-----------------(4D complex number: quaternion)------------>4D calculus
------------------(simplify)------------------------------------------>3D calculus
.
不同物理定律之间有类似的公式的原因：each analogous quantity was associated with the same unit of space(by Enzo Tonti)
.
1.1.2 Origins of Discrete Calculus
源于用graph theory来研究space
Kirchhoff用graph theory来研究electrical circuits
algebraic topology---->electrical circuits
electrical circuits     –---(相同结构（isomorphism?）)---->    conventional vector calculus
.
1.1.3 Discrete vs. Discretized
vector calculus关注的是analytical, closed-form solutions
discrete calculus关注的是algorithms for finding solutions
.
Discretized calculus（FEM）
.
1.2 Complex Networks
complex networks may be used to model a huge array of phenomena across all scientific and social disciplines.
.
-----------------------------------------------------------
Chapter 2
Introduction to Discrete Calculus
.
Gradient Theorem, Divergence(Gauss’s) Theorem, Curl(Stokes’) Theorem, Green’s Theorem
These expressions phrased in the language of vector calculus all share a common
structure that relates the vector fields to the topology of the underlying space in
a way that is independent of the dimension of the space.
.
Vector calculus ----(推广至任意维度)----> differential forms
∂<--->d : this exchange suggests a topological character of the derivative
.
2.2 Differential Forms
The generalization of the derivative provided by the theory of differential forms in arbitrary dimensions is motivated by the requirement that it must measure how a function changes in all directions simultaneously, just as df/dx measures how a function f changes in the x coordinate direction. 
This requirement leads directly to the antisymmetry property of differential forms and the exterior algebra that is based on the measurement of volume enclosed by a set of vectors
.
The exterior algebra of antisymmetric tensors motivates the exterior derivative for differential forms(指的是d(α∧β) = dα ∧β + (-1)($^k$)  α∧dβ)
.
2.2.1 Exterior Algebra and Antisymmetric Tensors
p-vectors and p-forms are special cases of antisymmetric tensors
.
exterior/wedge product ：∧ (欧氏空间下退化成cross product？)
inner product： <,> (欧氏空间下退化成dot product)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
在欧式空间，给定向量v1,v2,v3, 
- v1,v2,v3的exterior  product描述的是：向量张成的量(空间的体积)。
v1∧v2是平行四边形的面积(R2下的体积); 
v1∧v2∧v3是平行六面体的体积。
以前的方法是v1 ⨯ v2 • v3----需要预先定义⨯ 和• 。
相比之下，∧的表示方式更简洁(最初发明∧就是为了要描述多个向量张成的空间的体积)

- v1,v2,v3的inner  product描述的是：向量之间的夹角(line-up的程度)。
<v1, v2>是v1, v2的夹角。夹角越小，v1和v2 lineup的程度越大。
(v1, v2,v3的夹角(solid angle)如何计算？)

在非欧空间下，需要乘上g
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
.
v ̄, ω ̃: vector / form in general vector spaces
.
/\($^p$) V :={the space of p-vectors over V}: set of vector space; dimension= C($_n$)($^p$) (每一个组合表示一个维度(比如x ̄1∧x ̄2∧x ̄3表示一个维度， x ̄1 ∧x ̄3∧x ̄4表示另一个维度) )
/\($^p$) V($*$):={the space of p-forms over V($*$)}: set of form space; dimension= C($_n$)($^p$)
.
x ̄1 , x ̄2 , . . . , x ̄p are linearly dependent    <===>   x ̄1 ∧x ̄2 ∧ · · · ∧x ̄p = 0
.
a remarkable property of ∧  is its relationship to the determinant of a matrix.
Ax ̄1 ∧ Ax ̄2 ∧ · · · ∧ Ax ̄n = |A|( x ̄1 ∧ x ̄2 ∧ · · · ∧ x ̄n )
(可以这么理解：x ̄i是基坐标向量，Ax ̄i是x ̄i由矩阵A变换后的向量)
.
V($^∗$):={linear functional α ̃: V→R}: dual space of V;      (α ̃就是form)
V($^∗$)满足如下操作：(α ̃+β ̃)(v ̄) = α ̃(v ̄)+β ̃(v ̄),   cα ̃(v ̄) = cα ̃(v ̄)     (β ̃∈ V($^∗$), v ̄∈V )
.
定义【dual basis】 σ ̃1 , σ ̃2 , . . . , σ ̃n of V∗，满足： σ ̃($^i$)(e ̄j) = δij
可得σ ̃($^i$)(v ̄) = v($^i$)  (把v ̄的i-th分量抽取出来)
.
It is important to note that although forms are commonly thought of as supplying
a “measure” for vectors, they do not require a metric for their evaluation.
（而metric衡量的是距离度，所以 forms不需要衡量距离(所以forms是toplogy上的概念)。）
.
2.2.1.2 Manifolds, Tangent Spaces, and Cotangent Spaces
A general 【manifold is】 a topological space that is “locally Euclidean”.
A manifold consists of a collection or “atlas” of homeomorphisms to Euclidean
space called 【charts】.
.
x($^i$)   : coordinate functions
∂/∂x($^i$): tangent vectors
.
由v ̄ = ∑($_j$) v($^j$) ∂/∂x($^j$)，可把∂/∂x($^j$)看作TMnq上的正交基。
由σ ̃($^i$)(e ̄j) = δij，可把σ ̃($^i$) 看作另一个空间的正交基，由此定义了【cotangent space】T*Mnq
.
df(v ̄)|($_q$) ≡ v ̄($_q$)(f) = (D($_{v ̄}$)f)(q)
这表示：the differential df evaluated on the v ̄    is equivalent to    D($_{v ̄}$) evaluated on the function f。
特别的： 由dx($^i$) (∂/∂x($^j$)) = δij ，得dx($^i$) (v ̄) = v($^i$)  (把v ̄的i-th分量抽取出来) 这表示dx($^i$)是一组正交基；同时，由前面的σ ̃($^i$)得：dx($^i$) = σ ̃($^i$)
所以，any expression in terms of these basis elements  (e.g. ω ̃ = ω($_i$) dx($^i$)) is a differential form.
.
coordinate invariance:
v ̄ = 2e ̄1∧e ̄2 +3e ̄2∧e ̄3 −e ̄3∧e ̄1;
ω ̃ = 7σ ̃1∧σ ̃2 −6 σ ̃2∧σ  ̃3 +4σ ̃3∧σ ̃1;
ω ̃(v ̄)的值不随 e  ̄ i ∧ e  ̄ j 和 σ  ̃ i ∧ σ  ̃ j变化
.
.
2.2.1.3 The Metric Tensor: Mapping p-Forms to p-Vectors
contravariant v.s. covariant
contravariant quantities: e  ̄i, 
covariant quantities: ∂f/∂xi
.
计算ω ̃(v ̄)的值不需要引入metric，但是，forms <-------metric(tensor) makes an isomorphism-------> vector。
.
<v ̄, w ̄> = ∑i ∑j v($^i$) w($^j$) g($_{ij}$), 用矩阵表示为：<v ̄, w ̄> = v($^T$) G w     
<α ̃, β ̃> = ∑i ∑j  α($_i$) β($_j$) g($^{ij}$), 用矩阵表示为：<α ̃, β ̃> = a G($^{−1}$) b($^T$)
(G: primal metric tensor, G($^{−1}$) dual metric tensor)
.
isomorphism:
αj       = ∑i v($^i$) g($_{ij}
v$)^i($ = ∑i αj       g$)^{ij}
.
primal metric tensor： metric tensor on the tangent space
dual metric tensor：metric tensor on the cotangent space
.
metric-->向量之间的距离-->角度
.


.
2.2.2 Differentiation and Integration of Forms
closed form:     ω is closed if dω  ̃ = 0     (the kernel of d)
exact form:       α  is exact if     α ̃ = dβ ̃  (the image of d)
.
dω 的几何意义: the expansion of ω outwards in all directions(σ ̃($^i$)所表示的方向)
d  measures the variation of a p-form simultaneously in
each of the p directions of a p-dimensional parallelepiped, and is therefore
the natural generalization of the one-dimensional differential operator d/dt .
.
dω 的拓扑意义: ∫($_s$)  dω ̃ = ∫($_{∂s}$) ω ̃
.
p-domain: the domain of integration of a p-form
.
∫($_s$)  dω ̃ = ∫($_{∂s}$) ω ̃ 记为：[dω ̃, S]= [ω ̃, ∂S]，称d和∂是adjoint with respect to [,]
.
2.2.2.2 The Poincaré Lemma
ddω =0,  
∫($_s$)  ddω ̃ = ∫($_{∂s}$) dω ̃ = ∫($_{∂∂s}$) ω ̃ = 0
∂∂S = 0,
.
In the case of the exterior derivative, this identity is equivalent to the condition that mixed partial second derivatives are equal.(为什么？)
.
a closed form may be not exact
.
cohomology theory:  whether a closed form is exact
homology theory:  whether a closed region is the boundary of something
.
.
.
2.2.3 The Hodge Star Operator
若    ω ̃=              ∑($_{i,1,r}$)     w($_i$)       σ ̃($^i$)
则 *ω ̃= sqrt(|g|) ∑($_{i,1,r}$)     w($^*_i$)  (*σ ̃i)  (|g|: primal metric tensor determinant)
.
Hodge star operator has been recently extended to operate also on p-vectors,参见Harrison, J.: Geometric Hodge star operator with applications to the theorems of Gauss and
Green. Mathematical Proceedings of the Cambridge Philosophical Society 140(1), 135–155
(2006). doi:10.1017/S0305004105008716
。
         
HodgeStar的性质:  (given p-forms α ̃, β ̃, a scalar function f)
*α ̃ ∧ β ̃ = *β ̃ ∧ α ̃      (= scalar = <α ̃, β ̃> vol($^n$) , 为什么？  vol($^n$) = sqrt(|g|) dx1∧· · ·∧dxn) 
*(f α ̃) = f *α ̃
**(α ̃)= (−1)($^p(n−p)$) α ̃
****α ̃ = α ̃
α ̃ ∧*α ̃ = 0   iff   α ̃ = 0 (non-degeneracy of the inner product). 
*1= vol n
.
global scalar product (α ̃, β ̃) :
(α ̃, β ̃) ≡ ∫M  α ̃∧*β ̃ = ∫M  <α ̃, β ̃>  vol($^n$)    (M : compact manifold M($^n$))
.
in Euclidean metric:
u ̄ · v ̄ = *(u ̃∧ *v ̃) = *(v ̃ ∧ Hu ̃)
u ̄×v ̄ = *(u ̃ ∧ v ̃)
u  ̄ · (v ̄×w ̄) = *(u ̃∧v ̃∧w ̃)
.
∇ × α ̄ = *dα ̃    		(没有给出推导过程)
∇ · α  ̄ = *d*α ̃ (=-δα ̃    if M⊂R3, α ̃ is 1-form)(没有给出推导过程)
 (α ̄($^b$) = (α ̃) )
虽然计算里包含*，但并不需要求g。所以运算符× 和 ·  are purely topological in nature
。
2.2.3.1 The Codifferential Operator and the Laplace–de Rham Operator
【codifferential operator 】d($^∗$)： d($^∗$) ≡ (−1)($^{n(p+1)+1}$) *d*
δ≡d($^∗$)
.
(dα ̃, β ̃)= (α ̃ , δβ ̃)  ，称d和 δ是adjoint with respect to (,)
。
coclosed： δβ  ̃=0,
coexact： β ̃= δα ̃
。
δδ≡(−1)($^{n(p+1)+1}$) *d* (−1)($^{n(p+1)+1}$) *d* =(−1)($^{2n(p+1)+2}$) *d**d*
=*d**d*= *d (−1)($^p(n−p)$) d*= (−1)($^p(n−p)$) *dd* = (−1)($^p(n−p)$) *0*=0
.
Δ≡dδ+δd = (d+δ)^2
.
(Δα ̃, β ̃)= (α ̃ , Δβ ̃)  ，称Δ是self-adjoint with respect to (,)
.
harmonic form : Δω ̃ = 0
.
.
.
2.3 Discrete Calculus
2.3.1 Discrete Domains
A discrete domain will be represented by a 【cell complex】, which is comprised of a collection of finite dimensional vector spaces of 【p-cells】.
clique: a fully-connected set of nodes
σ($^p$): p-cell
Bp： p-ball
∂Bp
V：0-cells or nodes,
E：1-cells or edges
F：2-cells or faces
p-simplex： a p-cell consists of exactly p+1 vertices
p-clique: a clique comprised of p nodes
。
Note how this definition of a cell and its boundary excludes the possibility for the cell’s boundary
to self-intersect.
.
cell complex(simplical complex):
1. The boundary of each p-cell (for p > 0) is comprised of the union of lower-order p-cells.
2. The intersection of any two cells is either empty or a boundary element of both cells.(toplogy space的条件之一)
.
embedding及其目的：
Typically, the 0-cells of a complex are considered as vertices of a discrete manifold and as such are thought of as being embedded in some extrinsic embedding space, i.e., to each vertex is assigned a coordinate in n dimensions. This embedding of the vertices allows one to define other features of the complex, like orientation and duality (discussed below), in terms of the ambient space into which the complex is embedded.
。
2.3.1.1 Orientation

We consider two orientations to be the same (called 【coherent】) if one can be obtained from the other by an even permutation
。
vertex的orientation：
For completeness, a 0-cell is considered to have two orientations
(“sourceness” and “sinkness”) although it is defined by only a single node.Conven-
tionally, all nodes are given the same orientation, “sourceness”, meaning that the
negative (sink) end of an edge will not be coherent with the orientation of a node,
while the positive (source) end of an edge will be coherent with the orientation of a
node.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
为什么把edge 的起点设置为-1，终点设置为+1：
类比定积分∫f(x)dx = F(b) – F(a) 。起点a的系数是-1，终点b的系数是+1 
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
。
p-cell merge
.
2.3.1.2 The Incidence Matrix
.
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
discrete calculus的方法论：
把拓扑元素代数化（topology---->algebra）, 具体是：
1. 把拓扑结构(拓扑元素之间的(层级)连接关系)表示为matrix , 即Incidence Matrix N($_n$)($^T$)   (这里的层级关系就是boudnary关系)
2. 拓扑元素的权重表示为vector , 即p-chain τp
(p-chain 类比于被积函数f(x) ---- 在积分∫f(x)dx里dx|x=x0对积分结果的贡献是f(x0)dx，即dx|x=x0的权重是f(x0) )
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

。
2.3.1.3 Chains
【p-chain】τp：column vector， an n($_p$)-tuple of scalars which assigns a coefficient to each p-cell. 
(n($_p$): the number of distinct p-cells in the complex)
σ($_i$):  p-chain basis
C($_p$): the space of p-chain
。

2.3.1.4 The Discrete Boundary Operator
The incidence matrix  maps p-chains into their
corresponding boundary elements. In other words, when the incidence matrix N T p is
applied to a p-chain, the result is a (p−1)-chain：
τ($_{p−1}$) = N($_p$)($^T$) * τ($_p$)
Remarkably, this chain τ($_{p−1}$) represents the oriented set of (p−1)-cells on the
boundary of p-cells represented by the chain τp.
(比如，假设积分区域不包含p-cell A, 那么τ($_p$)不应该包含A的数据，则经过N($_p$)($^T$)变换后，τ($_{p−1}$)里也不会包含A的(boundary)数据。最终的效果就是，不会在A上做积分(因为A不在积分区域内)。可参考Fig.2.10)
Consequently, the incidence matrix is the matrix representation of the discrete boundary operator, i.e., N T p : C p →C p−1
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
p-chain 表示的就是p-cell
所以，τ($_{p−1}$) = N($_p$)($^T$) * τ($_p$) 的含义是：用(p-1)-cell表示p-cell
。
所以，N($_0$)($^T$) * N($_1$)($^T$) *...* N($_p$)($^T$)的含义是：
用(p-1)-cell表示p-cell,
....,
用edge-cell表示face-cell, 
用vertex-cell表示edge-cell, 
最终得出结果
。
所以，discrete calculus的思路：连续地取boundary，最终得出结果。
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 N($_p$)($^T$):  the boundary operator ∂p on p-chains
incidence matrix (Np)($^T$) is a natural representation of the boundary operator ∂ p on p-chains
.
The incidence matrix (Np)($^T$) provides：
(i) a representation (or data structure) of the topology of the discrete manifold
(ii) a representation of the boundary operator ∂p .
.
The oriented cell complex-----------------------------the entire domain
the chain τ($_p$)-----------------------------------------an oriented subdomain (the domain of integration) 
the incidence matrix------–----------------------------the boundary operator(e.g. A($^T$), B($^T$))
p-cochain c($^{p-1}$)-----------------------------------the  function assigning values to vertex/edge/face/...
incidence matrix's transpose (inverse?)-------------derivative operator(coboundary operator)  (e.g. A, B)
可参照Fig.2.20
.
.
2.3.2 Discrete Forms and the Coboundary Operator
【p-cochains】 c($^p$): a linear function defined on the domain of p-cells. C($_p$)-->R. 表示为n($_p$)×1 column vector c($^p$)

form: vector-->R
cochain: C($^p$) -->R
C($^p$): vector space of p-cochains
σ($^i$): p-cochain basis
。
there is a single basic p-chain and a single basic p-cochain defined at each p-cell of the complex,
and therefore the basis sets of p-cochains and p-chains are biorthogonal. For this reason, the two vector spaces are isomorphic.（为什么？）
。
 (在complex上的)积分变成了：
∑($_{σ^p}$)  applying p-cochain c($^p$) to p-chain τ($_p$) at p-cell σ($^p$)
= ∑($_{i, 1, n_p}$)  τ($_p$)(σ($_i$))  c($^p$)(σ($^i$)) 
:= [c($^p$), τ($_p$)]
。
定义 adjoint boundary operator (Np)($^{T*}$) 满足:
[(Np)($^{T*}$) c($^{p-1}$), τ($_p$)] = [c($^{p-1}$), (Np)($^T$) τ($_p$)]       (discrete version of Generalized Stokes’Theorem)
类比Generalized Stokes’Theorem，得：
【exterior derivative】 on p-cochains dp：dp = (∂($_{p+1}$) )($^*$) ≡ (N($_{p+1}$))($^{T*}$) = Np
。
.
2.3.3 Primal and Dual Complexes
我们对Dual Complexe的定义意味着定义了一个combinatorial manifold(局部同胚于欧式空间)
（详见Milnor, J.: On the relationship between differentiable manifolds and combinatorial mani-
folds. In: Collected Papers of John Milnor, vol. III: Differential Topology, pp. 19–28. Am.
Math. Soc., Providence (1956)）
。
Primal and Dual之间的incidence matrix的联系：
(N($_p$))($^T$) = M($_(n-(p-1))$)
this notion of duality is completely independent of the embedding
.
dual complex‘s orientation:
The combinatorial orientation of a primal cell has been termed intrinsic (since the orientation is defined by the cell nodes) 
while the orientation of a dual cell has been termed extrinsic (since this orientation is defined by the primal cell nodes)
.
2.3.4 The Role of a Metric: the Metric Tensor, the Discrete Hodge Star Operator, and Weighted Complexes
2.3.4.1 The Metric Tensor and the Associated Inner Product
g($^p$)($_{ii}$) := <σ($_i$), σ($_j$)>    (σ($_i$): the basis of C($_p$))
.
定义metric tensor G($_p$), C($_p$) -->C($^p$):   c($^p$) = G($_p$) τ($_p$)
Gp = diag(g($^p$)($_{ii}$))
.
p-chains a, b:
<a, b>  =  a($^T$) G b
.
p-cochains u, v:
<u, v>  =  u($^T$) G($^{-1}$) v
.
<a, b> = <G a, G b>
.
2.3.4.2 The Discrete Hodge Star Operator
Hodge Star *: C($^p$)-->C($^{n-p}$)
*x = G($_p$)($^{-1}$) x
x($^*$) := *x
.
2.3.4.4 The Volume Cochain
。
2.3.5 The Dual Coboundary Operator
dual coboundary operator, (Np)*:C($^p$)-->C($^{p-1}$)
(Np)* := * M($_{n-p+1}$) *
(Np)* = * (Np)($^T$) * = G($_{p−1}$) N($_p$) Gp($^{-1}$)
欧式空间下， (Np)* = (Np)($^T$)
。
2.3.6 The Discrete Laplace–de Rham Operator
Δ≡ dd∗ + d∗d
Lp = N($_p$) N($_p$)* + N($_{p+1}$)* N($_{p+1}$)
.
Lij = di, if i=j;     -1, if eij ∈ E;     0, otherwise    (di means node degree)
.
L = D − W = A($^T$) A    (D = {Dii=di})
.
for a weighted graph:
Lij = di/wi, if i=j;     -wij/wi, if eij ∈ E;     0, otherwise           (wi: node weight;  wij: edge weight )
.
L0: scalar Laplacian
L1: edge Laplacian
.
2.5 Examples of Discrete Calculus
scalar fields  ~   0-cochains
vector field   ~   1-cochains(a function assigning values to edges)
     ?               ~   2-cochains(a function assigning values to cycles)

2.5.1.1 Generalized Stokes’ Theorem on a 1-Complex
[Ac($^0$) , τ($_1$) ] = [c($^0$) , A($^T$) τ($_1$)]              （A=N($_1$)）
Fig. 2.20 的解释非常赞！
.
2.5.1.2 Comparison with Finite Differences Operators
discrete calculus v.s. FEM:
the central differences operator(模拟的是梯度) does not represent a boundary operator(所以无法满足微积分基本公式)
discrete calculus里的梯度是∇φ = (dφ)^#, 
。
2.5.1.3 Generalized Stokes’ Theorem on a 2-Complex
curl-theorem
[Bc($^1$) , τ($_2$) ] = [c($^1$) , B($^T$) τ($_2$)]              （B=N($_2$)）
Fig. 2.24, 用B($^T$) τ($_2$)得出边界
。
2.5.1.4 Generalized Stokes’ Theorem on a 3-Complex
div-theorem:
[N($_3$)c($^2$) , τ($_3$) ] = [c($^2$) , (N($_3$))($^T$) τ($_3$)] 
div-theorem(dual form):
[A($^T$) c($^1$) , τ($_0$) ] = [c($^1$) , Aτ($_0$)]
the divergence of the flow field c($^1$), given by A($^T$) c($^1$) , integrated over a region of nodes τ($_0$)  = the flow out of the region subtracted from the flow into the region.  (参见Fig. 2.25)
.
2.5.2 The Helmholtz Decomposition
cochain ~ vector field
。
c($^1$) = c($^1$)div-free + c($^1$)curl-free
Helmholtz decomposition的解不唯一，regularization后 可以得到唯一的解
。
2.5.3 Matrix Representation of Discrete Calculus Identities
discrete Gauss–Green formula:
c($^0$)($^T$) diag(τ($_0$)) (A($^T$) c($^1$))      (diag(τ($_0$))怎么理解？)
=(A diag(τ($_0$)) c($^0$))($^T$) c($^1$)    (分部积分，得下式)
=(A diag(τ($_0$)) c($^0$))($^T$) diag(τ($_{boundary}$)) c($^1$)    (edges connecting one  node in τ0(为什么？))
+(A diag(τ($_0$)) c($^0$))($^T$) diag(τ($_{interior}$))    c($^1$)    (edges connecting two nodes in τ0(为什么？))  
。
∇ × ∇u = 0         ～     B Ac($^0$) = 0
∇ · ∇ × F = 0      ～    AT BT c($^1$) = 0
(u: scalar field;  F: vector field)
general form of this Green’s identity：





2.5.4 Elliptic Equations
.
.
.
Chapter 3 Circuit Theory and Other Discrete Physical Models
xi∈R: the electric potential at a single node vi
yi∈R: the current passing through the edge ei
vector x=(x0,x1, ..., x($_{|v|}$)): node potentials     ~   0-cochain (node function).
vector y=(y0,y1, ..., y($_{|e|}$)): current                  ~   1-cochain
eij={vi, vj}: orientated edge, start from vi to vj
voltage pij = xi − xj
rij: resistance of eij
wij = 1/r ij:  conductance of eij
p: the voltage each edge.
bk：the voltage added to edge ek
fi ： current inserted into node vi
A0：reduced incidence matrix
ΔΔ：biharmonic operator
.
Ohm’s Law:                                   p = Gy             (    Gii = ri)
Kirchhoff’s Current Law (KCL):  A($^T$) y = 0    (all of the current flowing into a node also flows out of the node)
Kirchhoff’s Voltage Law (KVL):   Ax = p
Tellegen’s Theorem:                       p($^T$) y=x($^T$) A($^T$) y=0   (x is orthogonal to y)
.
Ohm’s Law+KCL +KVL ==>  A($^T$) G($^{−1}$) A x = L x = 0   (all of the node potentials will be equal (为什么？))
。
impedance：a generalized conception of the edge resistance
。
类比：
Symbolic ～Electrical circuit                                                ～Mass–spring network
x               ～electric potential                                               ～ mass displacement
p              ～voltage (potential difference)                            ～elongation
y              ～current responding                                            ～spring force

w              ～conductance (1/resistance)                                ～spring constant

v0              ～grounded node                                                 ～reference node
f                ～currents injected into nodes from ground        ～external forces on masses
G −1 p = y ～Ohm’s Law                                                      ～Hooke’s Law
A y = 0      ～Kirchhoff’s Current Law                                 ～conservation of forces
。
3.4.5 Linear Algebra Applied to Circuit Analysis
3.4.5.1 The Delta–Wye and Star–Mesh Transforms
delta–wye transform------推广-------->star–mesh transform.
delta–wye/ star–mesh  transform 类比于one step of Gauss–Jordan elimination on the Laplacian matrix （太牛了！）
。
In his Lecture Notes on Physics, Richard Feynman paused to consider why the same operators and equations recur throughout seemingly different areas of physics。
Feynman’s explanation is that the common thread tying together these physical phenomena is that the processes all occur in the same space and that this fact alone practically forces a certain relationship between variables.
In our discrete setting, Feynman’s explanation would suggest that the reason for the recurrence of these equations is that all of the phenomena are defined on a set of locations which are connected via
some neighborhood structure (i.e., a graph). Therefore, if we are going to describe a relationship between variables defined at the nodes, our basic tool set will have to reflect the space upon which these variables are defined. The operators of graph theory—the Laplacian matrix, adjacency matrix and incidence matrix—explicitly represent the space
。
。
Chapter 4    Building a Weighted Complex from Data
cycle set：a set of faces identified within a given graph
two edges are neighbors if they share a cycle
。
4.1.2.1 Defining Cycles Geometrically: Cycles from an Embedding
4.1.2.2 Defining Cycles Algebraically

The 【cotree】 subgraph corresponding to a tree subgraph is the (possibly disconnected) subgraph consisting of V and the set of the remaining edges Ecotree = E − Etree
。
Although the mean and median calculations appear to be
very different, we can view the median as a weighted mean

。
In the context of filtering, the assumption of this weighting strategy is that large magnitude gradients are likely to be signal and low magnitude gradients are likely to be noise,
The highfrequencies of a flow field are the components of the flow field having a projection
onto the high frequency eigenvectors of the edge Laplacian L1 = B($^T $)B + AA($^T$). Con-
sequently, the high-frequency components of the flow field may be decomposed into
those components of the flow field with a large curl and those components having a
large divergence.
。
the physical interpretation of the cycle weights G 2 and node weights G 0 as viscosity, which impedes fluid flow around cycles or through nodes.
。
。
5.1 Fourier and Spectral Filtering on a Graph
when we can apply standard Fourier methods to data defined on a graph？
The standard Fourier basis constitute the eigenfunctions of the Laplacian operator, and We expect that the columns of the Discrete Fourier Transform (DFT) matrix Q would  represent the eigenvectors of the Laplacian matrix.
Q will form the eigenvectors of the Laplacian matrix, if and only if the Laplacian matrix is circulant.
.
Theorem 5.1 The columns of the DFT matrix, Q , are eigenvectors of any circulant matrix, H .
.
a graph is called 【shift invariant】 if there exists a permutation of the node ordering such that the Laplacian matrix representing the graph is circulant. Therefore, any shift-invariant graph has the DFT basis as the eigenvectors of its Laplacian matrix.
.
regular graph: every node has the same number of neighbors
.
Fourier-based filtering has nothing to do with the graph topology as long as the graph is shift-invariant
。
Laplacian smoothing:
x [k+1] = x [k] − λ Lx [k] = x [k] − λ Q^T ∧ Qx [k]
Laplacian smoothing缺点是低频也会被光滑掉；为避免这个缺点，Taubin提出迭代：
x [k+1] = x [k] + μ Lx [k]    (μ > λ)
.
Many filtering methods may be viewed as procedures to minimize an energy

CH5 各种image filtering算法，可看作综述
。
by preserving the low frequencies, Taubin’s filtering approach avoids the shrinking observed from the other algorithms
。
The goal of a machine learning algorithm is to re-
duce a phenomenon of interest to a series of quantities that may be used to identify
the phenomenon and to generalize determinations made about the phenomenon to
other objects with a similar set of quantities.
。
Gaussian curvature(每个点的) is invariant under isometric transformations of the surface. That is, if the surface is deformed in a way that does not affect the distance between any pair of vertices on the surface, then the Gaussian curvature is also unaffected. For this reason, the Gaussian curvature is called intrinsic and depends only on the metric of the surface.

total curvature
-----------------------------------------

¹²³⁴⁵⁶⁷⁸⁹ ᵃᵇᵈᵉᶠᵍʰⁱʲᵏˡᵐⁿᵒᵖ ʳˢᵗᵘᵛʷˣʸᶻ ᵅᵝᵞᵟᵠ     ₀₁₂₃₄₅₆₇₈₉ ₐ   ₑ  ₕᵢⱼₖₗₘₙₒₚ ᵣₛₜᵤᵥ ₓ   ᵦ
º¹²³⁴ⁿ₁₂₃₄·∶αβγδεζηθικλμνξοπρστυφχψω∽≌⊥∠⊙∈∩∪∑∫∞≡≠±≈＄㏒㎡㎥㎎㎏㎜
∈⊂∂Δ
∧H   







---REF--------------------------------------------------------
Barabasi, A.L.: Linked: How Everything Is Connected to Everything Else and What It Means
for Business, Science, and Everyday Life. Plume, Cambridge (2003)
64. Buchanan, M.: Nexus: Small Worlds and the Groundbreaking Theory of Networks. Norton,
New York (2003)
Chen, Y., Dong, M., Rege, M.: Gene expression clustering: A novel graph partitioning ap-
proach. In: Proceedings of International Joint Conference on Neural Networks (2007)
Watts, D.J.: Six Degrees: The Science of a Connected Age. Norton, New York

335. Schutz, B.F.: Geometrical Methods of Mathematical Physics. Cambridge University Press,
Cambridge (1980)
Munkres, J.R.: Elements of Algebraic Topology. Perseus Books, Cambridge (1986)
Frankel, T.: The Geometry of Physics: An Introduction, 2nd edn. Cambridge University
Press, Cambridge (2004)
Flanders, H.: Differential Forms. Academic Press, New York (1963)
Darling, R.: Differential Forms and Connections. Cambridge University Press, Cambridge
(1994)

Hestenes, D.: Space-Time Algebra. Gordon and Breach, New York (1966)
Jancewicz, B.: The extended Grassmann algebra of R 3 . In: Baylis, W.E. (ed.) Clifford (Geo-
metric) Algebras with Applications to Physics, Mathematics, and Engineering, pp. 389–421.
Birkhäuser, Boston (1996). Chap. 28
Weinreich, G.: Geometrical Vectors. University of Chicago Press, Chicago (1998)
Warnick, K.F., Selfridge, R.H., Arnold, D.V.: Teaching electromagnetic field theory using
differential forms. IEEE Transactions on Education 40(1), 53–68 (1997)
178. Gross, P.W., Kotiuga, P.R.: Electromagnetic Theory and Computation: A Topological Ap-
proach. Cambridge University Press, Cambridge (2004)
47. Bossavit, A.: Computational Electromagnetism. Academic Press, San Diego (1998)
353. Spivak, M.: A Comprehensive Introduction to Differential Geometry, vol. 1, 3rd edn. Publish
or Perish, Houston (2005)


275. Mattiusi, C.: The finite volume, finite difference, and finite elements methods as numerical
methods for physical field problems. Advances in Imaging and Electron Physics 113, 1–146
(2000)
323. Roth, J.P.: An application of algebraic topology to numerical analysis: On the existence of
a solution to the network problem. Proceedings of the National Academy of Sciences of the
United States of America 41(7), 518–521 (1955)
360. Strang, G.: Computational Science and Engineering. Wellesley-Cambridge Press, Wellesley
(2007)
79. Tonti, E.: On the geometrical structure of the electromagnetism. In: Gravitation, Electromag-
netism and Geometrical Structures, for the 80th Birthday of A. Lichnerowicz, pp. 281–308.
Pitagora Editrice, Bologna (1995)
323. Roth, J.P.: An application of algebraic topology to numerical analysis: On the existence of
a solution to the network problem. Proceedings of the National Academy of Sciences of the
United States of America 41(7), 518–521 (1955)
178. Gross, P.W., Kotiuga, P.R.: Electromagnetic Theory and Computation: A Topological Ap-
proach. Cambridge University Press, Cambridge (2004)