5月10日@实验室LSI矩阵分解CUDA技术gt

1、12012年5月10日实验室2讲个例子，看看理解对不对cite: http:/ 3lsi (latent semantic indexing)隐语义索引隐语义索引 设doc1, doc2, doc3是三个文件. 一些术语在这三个文件中的出现情况如下表: doc1 doc2 doc3-access x document xretrieval x xinformation x* x*theory xdatabase xindexing xcomputer x* x*-这里, 假定用information 和computer作为主题词进行检索, 那么doc2和doc3与之精确匹配, 因而中选. 然而

2、, doc2是用户并不想要的文件, doc1才是想要的查不出来.问题：由于一词多义, 基于精确匹配的检索算法会报告许多用户不要的东西; 由于一义多词,基于精确匹配的检索算法又会遗漏许多用户想要的东西。4继续继续1首先, 以术语(terms)为行, 文件(documents)为列做一个大矩阵(matrix). 设一共有t行d列, 矩阵名为x. 矩阵的元素为术语在文件中的出现频度. 数学上可以证明: x可以分解为三个矩阵t0, s0, d0(d0的转置)的积. 其中t0和d0的列向量都是正交归一化的, s0是对角矩阵. t0是t*m矩阵, s0是m*m矩阵,d0是d*m矩阵,m是x的秩. 这种分解

3、叫做单值分解(singlar value decomposition,简称svd).x=t0*s0*d0一般要求t0, s0, d0都是满秩的. 不难做到把s0的元素沿对角线从大到小排列.现在, 把s0的m个对角元素的前k个保留, 后m-k个置0, 我们可以得到一个新的近似的分解:xhat=t*s*d xhat在最小二乘意义(?)下是x的最佳近似! 这样, 我们实际上有了一个降维的途径 5继续继续2(?)1. 做“正向”乘法:xhat * xhat = t * s * d * d * s * t = t * s2 * t(d * d = i, 因为d已经是正交归一的). 它的第i行第j列表明了

4、术语i和j的相似程度.2. 做“逆向”乘法:xhat * xhat = d * s * t * t * s * d = d * s2 * d(t * t = i, 因为t已经是正交归一的). 它的第i行第j列表明了文件i和j的相似程度.3. 比较一个文件和一个术语恰巧就是xhat本身. 它的第i行第j列表明了术语i和文件j的相关联程度. application:可以把主题词的集合认为是一个虚拟的文件. 查询的任务说白了是把这个虚拟的文件和其他文件做相似性比较, 挑选最相似的出来(挑选到什么程度打住, 要看实际问题的要求）6我的理解我的理解1.把一个大矩阵拆解成简单矩阵2.把两个大矩阵计算变成简

5、单矩阵间的计算7svd(singlar value decomposition)nmf(non-negative matrix factorization )cite:the relationships among various nonnegative matrix factorization methods.pdf矩阵的三角分解（cholesky分解、lu分解等）矩阵的正交三角分解(qr分解等)矩阵的满秩分解(?)矩阵的奇异值分解(svd)cite: http:/ 8我的理解我的理解11.svd分解拆解为：两个相互正交矩阵和一个对角矩阵2.qr分解拆解为：一个正交矩阵和一个上三角矩阵3.l

6、u分解拆解为：一个上三角矩阵和一个下三角矩阵4.cholesky分解(?)5.nmf分解拆解为：两个非负矩阵6.。我的问题：是不是存在某种分解是基于另一种分解的？比如先拆成两个矩阵，再把其中某个再拆解。或者.note：区分矩阵元素的正负近似解9我的理解我的理解2我目前遇到的应用：图像降维重构(?)数据挖掘算法：聚类k-means文本挖掘社会网络分析10矩阵分解的具体算法矩阵分解的具体算法还没有学习。海洋和远帅希望能做补充。比如对稀疏（sparse）和密集（dense）矩阵不同的算法。11我的工作我的工作矩阵分解矩阵分解&并行计算并行计算概况概况常用的线性代数数学库基于多核多处理器以及机

7、群的数学库基于gpu并行加速的解决方案12常用的线性代数数学库blasbasic linear algebra subprograms(fortran)一个最基础的库，其他软件在对它进行优化atlasautomatically tuned linear algebra software(c and fortran)对bals加强，提供更加灵活的接口lapacklinear algebra package(c and fortran)对blas进行封装，提供专门对矩阵的处理接口比如：matrix factorizations (lu, cholesky, qr, svd, schur, gene

8、ralized schur)缺点：慢，调用难cublas nvidia cuda basic linear algebra subroutinescuda版本的基础线性代数库13基于多核多处理器以及机群的数学库基本上是根据硬件对blas的进行定制：mklintel math kernel libraryintel处理器数学库核心acmlamd core math library (acml)amd处理器数学库核心gotoblas2多处理器并行化提高效率plasma多核处理器并行化缺点：还是不够快，没有考虑gpu的优势14基于gpu并行加速的解决方案svd_1张舒没有源代码qr-svd 没有源代

9、码赵佳只是个ppt，没有源代码/zhaojia/fast svd on graphics processors没有源代码/numeric/svd/ isvd-cuda没有源代码http:/ 15基于gpu并行加速的解决方案svd_2cula一个商业软件，功能齐全，dense版本是免费cula是lapack的cuda版主要功能：linear equationsorthogonal factorizationsleast squares solverssymmetric eigenproblemsnonsymme

10、tric eigenproblemssingular value decompositionnote:自己编写代码，可以成功运行缺点：商业软件，无法获得源代码16基于gpu并行加速的解决方案svd_3magma一个开源软件，功能齐全magma也是lapack的cuda版解决:lu, qr, and cholesky factorizations svdeigen and singular value problem note:需要和atlas或者gotoblas2搭配使用还没写出矩阵分解程序。接口没搞懂。17基于gpu并行加速的解决方案nmf求解：nmfgpumlib提供nmf计算，接口不清晰

11、，需摸索nmf-cuda某个图像研究生的程序，但是功能不清晰修改过代码，可以跑18总结总结软件基本都是linux安装复杂，依赖关系复杂显然有部分人实现了矩阵分解的cuda并行化，但是没有公开代码，根据论文描述，似乎还并不太完善。功能丰富的软件例如magma和cula都有各自不足。商业软件，不开放源代码，无法全面评估，以及适用于研究领域，不具开源优势。magma是开源中做得最好的，但是对别的软件依赖性太强，光是安装就花费了两天时间才摸索出来。没有一个软件能让我们diy。我们必须借鉴他们的已有做法，从基础库开发，实现cuda版本。19下一步下一步学习分解算法或者根据一个应用实例，在找到的源代码基础上修改。20reference:1.singular value decomposition on gpu using cuda2.lu, qr and cholesky factorizations using vector capabilities of gpus3.a gpu-based approximate svd algorithm4.non-negative matrix factorization implementation using graphic processing units5.the relationship