-
Near-Linear time Laplacian Equation Solver
Introduction Graph $G$의 Laplacian은 많은 graph problem에 관여하는 중요한 object입니다. 과거 Matrix-Tree theorem에 대해 다룬 글에서 볼 수 있듯 Laplacian의 determinant는 $G$의 스패닝 트리 개수와도 관계가 있고, 오늘 다룰 Laplacian system을 푸는 것도 굉장히 중요한 문제입니다. 또한 Laplacian의 고유값(eigenvalue)들 또한 graph의 well-connectedness와 관련이 있는 유의미한 지표로 사용할 수 있습니다. 정점이 $n$개, 간선이 $m$개인 무방향 그래프 $G$의 Laplacian $L _ {G}$는 $D - A$로 정의합니다. 여기서 $D$는 $D _ {i, i} = \deg(i)$를 만족하는 대각행렬이고, $A$는...
-
Nearly optimal communication complexity of Bipartite Maximum Matching
Introduction Bipartite Maximum Matching (BMM)은 Bipartite graph $(V = X \sqcup Y, E \subseteq X \times Y)$에 대해 크기 $F$ 이상인 Matching이 존재하는지를 묻는 decision problem, 혹은 Maximum Matching의 크기를 계산하는 문제를 이야기합니다. 굉장히 오래 전부터 연구되어 온 문제이고, 정점이 $n$개, 간선이 $m$개인 BMM은 $m^{1 + o(1)}$ 시간 안에 해결할 수 있다는 것이 알려졌습니다. 원본 문제의 시간 복잡도가 subpolynomial 수준에서 사실상 optimum을 달성했기 때문에, 비전형적인 세팅에서 BMM을 해결하는 기법들이 등장하기 시작했습니다. 그 예시가 multi-party communication으로,...
-
Kirchhoff's Theorem (Matrix-Tree Theorem)
이번 글에서는 그래프의 스패닝 트리의 개수를 세는 두 가지 정리, Cayley’s formula와 Kirchhoff’s theorem에 대해 소개합니다. Cayley’s Formula 일반 그래프의 스패닝 트리의 개수를 세어보기에 앞서, 특수한 경우부터 먼저 살펴봅시다. Theorem 1 (Cayley’s Formula). $n$개의 정점으로 이루어진 완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다. 이 정리를 증명하는 방법으로는 여러 가지가 알려져 있으며, 대표적으로 Prüfer sequence와의 일대일 대응 관계를 찾는 증명이 있습니다. 개인적으로 가장 마음에 드는 증명은 다음과 같은 더블 카운팅을 이용한 증명입니다. 책 “하늘책의 증명” (Proofs from...
-
Shortest Even Length Cycle in Digraphs
Introduction 문제 해결을 하다 보면 종종 몇 가지 조건들을 더하고 빼며 문제를 확장시키거나, 더 포괄적인 문제를 해결합니다. 지난 글 에서는 추상화를 통해 문제를 확장하는 일련의 과정을 느낄 수 있었습니다. 이번에는 반대로 원하는 답에 몇 가지 추가적인 조건을 덧붙여 구체화된 문제를 어떻게 해결하는지 들여다보도록 합시다. “단순 무방향 그래프 $G$에 사이클이 존재하느냐?” 라는 기초적인 질문에서 출발합니다. DFS를 이용하여 해결할 수 있는 문제죠. 이 문제만 해도 몇 가지 방향으로 확장할 수 있습니다. 최소 길이: “$G$에 길이가 $k$ 이하인...
-
Characteristic Polynomial in a Commutative Ring
Introduction $n \times n$ 정사각행렬 $A = (a _ {ij})$가 주어져 있을 때, $A$의 determinant $\det A$는 아래와 같이 계산할 수 있습니다. \[\det A = \sum _ {\sigma \in S _ {n}} \mathrm{sgn}(\sigma) \cdot \prod _ {i = 1}^{n} a _ {i \sigma _ {i}}\] 오늘은 $\det A$ 와, 그를 일반화하는 특성다항식(Characteristic polynomial) $\phi _ {A}(x) = \det(x I - A) = x^{n} - \mathrm{tr} (A) x^{n-1} + \cdots + (-1)^{n-1} \det A$를 계산하는 방법을...
-
ESPiRiT을 이용한 Sensitivity Computation
Introduction 지난 글에서는 MRI의 개괄적인 원리, 즉 장비에서 얻은 raw data를 어떻게 이미지로 변환하는지에 대해 다루어보았습니다. 또한 그 중에서 scan time을 줄이기 위한 기법인 Parallel imaging과, 그로 인한 이미지 퀄리티 저하를 보상하는 알고리즘 중 SENSE, GRAPPA, 그리고 PRUNO에 대해 간략히 다루었습니다. 현재 가장 두루 쓰이는 방법은 GRAPPA, SENSE이지만 이 둘은 벌써 고안된 지 20년이 넘어가는 classic한 알고리즘입니다. Practical하진 않지만, 연구나 다른 특수한 목적으로 개발된 고성능 알고리즘들이 쏟아져나왔죠. 오늘은 그 중에서 수학적으로도 흥미롭고, 꽤 재미있는 인사이트를...
-
MRI imaging과 Parallel Imaging Algorithm, 그리고 PRUNO
Introduction MRI (Magnetic Resonance Imaging)은 X-Ray, CT와 함께 널리 쓰이는 의료 영상 기법으로 손꼽힙니다. 이미지 특성 상 가장 좋은 연부 조직 대비 (soft matter contrast)를 보여줍니다. 즉, 근육이나 뇌 등 수분을 많이 포함하는 조직에 대해 가장 월등한 이미지 품질을 낼 수 있습니다. 다만 MRI의 경우 짧게는 30분에서 1시간 정도 되는 긴 촬영 시간이 단점으로 꼽히는데, 때문에 시간 단축을 위한 다양한 기법이 제시되고 있습니다. MRI는 촬영한 raw data가 전자기파 신호이기 때문에, 특이하게도 이를 푸리에 변환을 비롯한...
-
XOR 관련 문제를 푸는 접근법들
들어가기 전에 XOR (bitwise exclusive or)은 대표적인 bit 연산 중 하나입니다. 다른 bit 연산인 AND,OR,NOT이 갖지 못하는 특성 때문에, PS 및 CP에서도 관련 문제가 심심치 않게 출제되곤 합니다. 하지만 문제 제목이나 지문에 XOR이 있으면 일단 긴장하거나, 기피하시는 분들도 꽤 자주 본 것 같습니다. 그래서, 이번 글에서는 이런 XOR 관련 문제들에 접근하는 방법 몇 가지를 설명해 보려고 합니다. Basic Part 본격적으로 들어가기에 앞서, XOR 연산이 가지고 있는 성질 몇 가지에 대해서 간단하게 짚고 넘어가려고 합니다. 여러...
-
행렬 분해(Matrix Decomposition)
행렬 분해(Matrix Decomposition) 행렬 분해(matrix decomposition)는 여러 특정 구조를 가진 행렬들의 곱으로 기존의 행렬을 나타내는 것을 의미합니다. 예를 들어, $ A = \begin{bmatrix} 1 & 2 & 3 \ 2 & 4 & 6 \ 3 & 6 & 9 \end{bmatrix}$ 와 같은 행렬을 생각해 봅시다. 이 경우 $ A $를 아래와 같이 $ 3 \times 1 $ 크기의 두 행렬과 $ 1 \times 1 $ 크기의 대각 행렬 을 통해 나타낼 수 있습니다. $...
-
Berlekamp-Massey 알고리즘의 이해와 응용
Berlekamp-Massey 알고리즘의 이해와 응용 Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다. 이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지...