# A Physicist's View on Partial 3D Shape Matching
## 3 Implementation
### Solving the Balanced and Unbalanced Optimal Transport Problems  
Implementations of the physics-based approaches to solving the balanced and unbalanced OT problems are similar, and follow Algorithm 1. We note first that the procedures described in Sections 2.4 and 2.5 provide a scheme for computing the transportation plan between two sets of points at a given finite temperature \(T\) (or equivalently at a given \(\beta\) value, where \(\beta=1/T\)). This temperature can be seen as a regularization parameter, and the actual optimal transportation plan is obtained when \(\beta\to+\infty\). It is possible to run the procedure directly at a low temperature. We found, however, that it is best to use an annealing procedure, starting with small \(\beta\) and gradually increasing this parameter [47; 54]. The solution at a given \(\beta\) serves as input for the following \(\beta\) value. This annealing procedure is efficient as we know that the mean field energy values are monotonic functions of \(\beta\).  
```
Input: The two sets of points \(S_{1}\) and \(S_{2}\), the cost matrix \(C\) between \(S_{1}\) and \(S_{2}\). Initial value \(\beta_{0}\) for \(\beta\). For the balanced OT problem, the masses \(m_{1}\) and \(m_{2}\) associated with \(S_{1}\) and \(S_{2}\), respectively Initialize: Initialize arrays \(\lambda\) and \(\mu\) to \(0\), and initialize \(x=0\) (unbalanced OT). Set \(\beta^{0}=\beta_{0}/STEP\), where \(STEP\) is set to \(\sqrt{10}\). for\(k=1,\ldots\) until convergence do (1) Initialize \(\beta^{k}=STEP*\beta^{k-1}\). (2) Solve the system of non linear Equations ( Equation (14) for balanced, Equation (25) for unbalanced OT) for \(\lambda\), \(\mu\) and \(x\) at saddle point (3) Compute optimal transport plan \(G_{\beta}^{MF}\), and \(U^{MF}(\beta^{k})\). For unbalanced OT, compute masses \(m_{1}^{MF}\), \(m_{2}^{MF}\). (4) Check for convergence: if \(|U^{MF}(\beta^{k})-U^{MF}(\beta^{k-1})|/U^{MF}(\beta^{k-1})<TOL\), stop endfor Output: The converged transport plan \(G_{\beta}^{MF}(k,l)\), the corresponding transport cost \(U^{MF}(\beta)\). For unbalanced OT, the optimized masses \(m_{1}^{MF}\), \(m_{2}^{MF}\).
```  
**Algorithm 1** A temperature-dependent framework for solving the balanced or unbalanced optimal transport problem.  
At each \(\beta\) value, the nonlinear systems of equations defined by Equations (14) and (25) for the balanced and unbalanced OT problem, respectively, are solved using an iterative Newton-Raphson method [47; 54]. Once the system is solved, the optimal transportation plan \(G_{\beta}^{MF}\) and the corresponding transport energy \(U^{MF}(\beta)\) are computed. If the latter has converged, i.e., does not differ from the value at the previous \(\beta\) value more than a tolerance TOL, the program is terminated as the method is thought to have converged.  
The primary computational cost of this algorithm is associated with solving the nonlinear systems of equations, which needs to be repeated at each value of \(\beta\). We use an iterative Newton-Raphson method that solves a linearized system of equations at each iteration. We tested both a direct solver based on LU decomposition and an iterative conjugate gradient (CG) method to solve this system. This will be discussed in the results section, under the computing time considerations.